ManachersAlgorithm.swift

func manachersAlgorithmLeetcode(_ s: String) -> String {
  let sPrime = ["#"] + s.map { String($0) }.joined(separator: "#").map { String($0) } + ["#"]
  let n = sPrime.count
  var palindromeRadii = Array(repeating: 0, count: n)
  var center = 0
  var rightBound = 0
  var maxLength = 0
  var maxIndex = 0
  
  for i in 1..<n {
    let mirror = 2 * center - i
    let leftBound = center - (rightBound - center)
    // center = (l + r) / 2
    // center * 2 = l + r
    // center * 2 - r = l
    // l = center * 2 - r
    print(sPrime.joined())
    var padding = Array(repeating: " ", count: n)
    padding[rightBound] = "r"
    padding[center] = "c"
    padding[i] = "i"
    padding[leftBound] = "l"
    
    if mirror >= 0 {
      padding[mirror] = "m"
    }
    
    print(padding.joined())
    
    // If we are within the bounds of the palindrome centered at `center`
    if i < rightBound {
      // We can know that the radius of the palindrome at i at least the same as
      // the palindrome at mirror as long as the palindrome at mirror is within the bounds
      // of the palindrome at center, otherwise restrict the size to the bounds of the
      // palindrome at center
      palindromeRadii[i] = min(rightBound - i, palindromeRadii[mirror])
    }
    
    // Search outwards from there, since the palindrome could be larger
    while
      i + 1 + palindromeRadii[i] < n
      && i - 1 - palindromeRadii[i] >= 0
      && sPrime[i + 1 + palindromeRadii[i]] == sPrime[i - 1 - palindromeRadii[i]]
    {
      palindromeRadii[i] += 1
      if palindromeRadii[i] > maxLength {
        maxLength = palindromeRadii[i]
        maxIndex = i
      }
    }
    
    // If the palindrome at i extends past the right bound of the palindrome at center
    if i + palindromeRadii[i] > rightBound {
      // Update the center and the new furthest known rightbound
      center = i
      rightBound = i + palindromeRadii[i]
    }
  }
  
  let centerIndex = maxIndex
  let startIndex = (centerIndex - maxLength) / 2
  let longestPalindrome = s.map(String.init)[startIndex..<startIndex+maxLength].joined()
  
  return longestPalindrome
}