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 once to check for palindrome properties. If a mismatch is found, it performs two additional substring checks, each of which can take O(n) time in the worst case. However, since these checks are only performed once per mismatch, the overall complexity remains O(n).
The space complexity is O(n) as well, primarily due to the creation of the two substrings `skipL` and `skipR` when a mismatch is detected. Each of these substrings can be as long as n in the worst case, leading to a linear space requirement. If we ignore the space used for the input string, the additional space used by the function is still O(n) due to these substrings.
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