Jun 27, 20241 min readThe time complexity of the `validPalindrome` function is O(n), where n is the length of the input string `s`. This is because in the worst case, the function may need to traverse the entire string to check for palindrome properties, which involves comparing characters from both ends towards the center. If a mismatch is found, it performs two additional substring checks, each of which can also take O(n) time in the worst case. However, since these checks are only performed once per mismatch, the overall complexity remains linear.
The space complexity is O(n) as well, primarily due to the creation of two substrings (`skipL` and `skipR`) when a mismatch is detected. Each of these substrings can be up to the length of the original string in the worst case, leading to the linear space usage. If we ignore the space used for the input string, the auxiliary space used by the function itself is constant, O(1), but the overall space complexity is dominated by the substring allocations.
there is only one pair of i, j such that s.charAt(i) != s.charAt(j)
after the different pair hit, we try removing i or j, the characters in middle should be a palindrome.
there is no pair of i, j such that s.charAt(i) != s.charAt(j)
Code
class Solution: def validPalindrome(self, s: str) -> bool: left, right = 0, len(s) - 1 while left < right: if s[left] != s[right]: skipL, skipR = s[left + 1:right + 1], s[left:right] return skipL == skipL[::-1] or skipR == skipR[::-1] left, right = left + 1, right - 1 return True