swift string advancedBy is slow? -

so writing in swift practice online judge.

here's issue: longest palindromic substring

given string s, find longest palindromic substring in s. may assume maximum length of s 1000, , there exists 1 unique longest palindromic substring.

so using dp solve in swift:

class solution {     func longestpalindrome(s: string) -> string {         var hash = array(count: s.characters.count, repeatedvalue: array(count: s.characters.count, repeatedvalue: false))         in 0 ..< s.characters.count {             hash[i][i] = true         }         var maxstart = 0         var maxend = 0         var maxcount = 1         in 1.stride(through: s.characters.count - 1, by: 1) {             j in 0 ..< s.characters.count - 1 {                 if j + < s.characters.count {                     if isvalidpalindrome(j, j + i, s, hash) {                         hash[j][j + i] = true                         if maxcount < + 1 {                             maxcount =                             maxstart = j                             maxend = j +                         }                     }                 }                 else {                     break                 }             }         }          // construct max palindrome string, swift string dummy         var str = ""         in maxstart...maxend {             let index = s.characters.startindex.advancedby(i)             str += string(s.characters[index])         }         return str     }      func isvalidpalindrome(start: int, _ end: int, _ s: string, _ hash: [[bool]]) -> bool {         // end <= s's length - 1         let startindex = s.startindex.advancedby(start)         let endidnex = s.startindex.advancedby(end)         if end - start == 1 {             return s[startindex] == s[endidnex]         }         else {             let left = start + 1             let right = end - 1             return s[startindex] == s[endidnex] && hash[left][right]         }     } } 

i thinking it's correct one, when submit, time exceeded long strings like:

"kyyrjtdplseovzwjkykrjwhxquwxsfsorjiumvxjhjmgeueafubtonhlerrgsgohfosqssmizcuqryqomsipovhhodpfyudtusjhonlqabhxfahfcjqxyckycstcqwxvicwkjeuboerkmjshfgiglceycmycadpnvoeaurqatesivajoqdilynbcihnidbizwkuaoegmytopzdmvvoewvhebqzskseeubnretjgnmyjwwgcooytfojeuzcuyhsznbcaiqpwcyusyyywqmmvqzvvceylnuwcbxybhqpvjumzomnabrjgcfaabqmiotlfojnyuolostmtacbwmwlqdfkbfikusuqtupdwdrjwqmuudbcvtpieiwteqbeyfyqejglmxofdjksqmzeugwvuniaxdrunyunnqpbnfbgqemvamaxuhjbyzqmhalrprhnindrkbopwbwsjeqrmyqipnqvjqzpjalqyfvaavyhytetllzupxjwozdfpmjhjlrnitnjgapzrakcqahaqetwllaaiadalmxgvpawqpgecojxfvcgxsbrldktufdrogkogbltcezflyctklpqrjymqzyzmtlssnavzcquytcskcnjzzrytsvawkavzboncxlhqfiofuohehaygxidxsofhmhzygklliovnwqbwwiiyarxtoihvjkdrzqsnmhdtdlpckuayhtfyirnhkrhbrwkdymjrjklonyggqnxhfvtkqxoicakzsxmgczpwhpkzcntkcwhkdkxvfnjbvjjoumczjyvdgkfukfuldolqnauvoyhoheoqvpwoisniv" 

i can correct result qahaq after time, , wondering why it's slow. if write in other language, not bad.

i suspect api s.startindex.advancedby(start) causing it, checked doc, no time complexity , no other ways turn int startindex type?

any ideas replace advancedby? thank in advance.

for having same issue: turned swift string array, , gets faster.

i looked swift source code advancedby implementation, it's o(n) opreation, that's why it's slow.

for whom interested in implementation, take @ https://github.com/apple/swift/blob/8e12008d2b34a605f8766310f53d5668f3d50955/stdlib/public/core/index.swift

you see advancedby merely multiple successor():

  @warn_unused_result   public func advanced(by n: distance) -> self {     return self._advanceforward(n)   }   /// not use method directly; call advanced(by: n) instead.   @_transparent   @warn_unused_result   internal func _advanceforward(_ n: distance) -> self {     _precondition(n >= 0,         "only bidirectionalindex can advanced negative amount")     var p = self     var : distance = 0     while != n {       p._successorinplace()       += 1     }     return p   }