Problem overview
The function isPalindrome takes a String named input and returns a Boolean: true if the string reads the same forwards and backwards, false otherwise. The statement asks for O(n) time and O(1) extra space.
In the first example, "madam racecar madam" is a palindrome. The first and last characters are both m, the second and second to last are both a, and so on, all the way to the space in the middle that matches itself. "abcbx" is not: its first character a differs from its last, x.
The check is literal. Spaces count as characters, and A and a are different characters, so "Aba" is not a palindrome.
Approach: compare from both ends
If a string has length n, it is a palindrome exactly when input[0] == input[n - 1], input[1] == input[n - 2], and so on for every pair of mirrored positions. The simplest idea is to build a reversed copy and compare it with the original. That works, but the copy takes O(n) extra space, which the statement rules out.
Two pointers avoid the copy. One pointer starts at the first index and one at the last. They compare their characters and move one step towards each other. As soon as a pair differs, the answer is false. If the pointers meet or cross without a mismatch, every pair matched and the answer is true.
Each pair is checked once, from the outside in, so the work is linear. Only two integers are stored, so the extra space is constant.
Here is the idea on "abcbx". The pointers start at indices 0 and 4, which hold a and x. They differ, so the function returns false right away, without looking at the middle. On "abcba" the pairs a/a and b/b match, the pointers meet at index 2, the loop ends and the function returns true.
Step by step
- Create
leftas avarset to 0, the first index. It must be avarbecause it changes in the loop. - Create
rightas avarset toinput.length - 1, the last index. - Loop while
left < right. While the pointers haven't met, there is still a pair to compare. With an odd length, the middle character is never compared, which is fine because it matches itself. - Return
falseon a mismatch. Ifinput[left] != input[right], one bad pair is enough to decide the answer. - Move both pointers inward with
left++andright--. Without this, the loop would compare the same pair forever. - Return
trueafter the loop. The code only gets here if every pair matched.
The solution in Kotlin
class Solution {
fun isPalindrome(input: String): Boolean {
var left = 0
var right = input.length - 1
while (left < right) {
if (input[left] != input[right]) {
return false
}
left++
right--
}
return true
}
}
Kotlin details worth knowing:
- Indexing a string gives a
Char.input[left]is a single character, and comparing twoCharvalues with!=compares the characters themselves. !=compares contents. In Kotlin,==and!=callequals, so they test equality of values, not whether two references are the same object. That is what you want for characters and also for whole strings.- Strings are immutable. The function only reads
input, so nothing is copied or changed. varversusval.leftandrightare reassigned, so they must bevar. Avalcould be set once only.- The early
return. Returning from inside the loop ends the function immediately, so a string that differs at its ends is rejected after one comparison. - Characters are UTF-16 units. A character outside the basic range, such as many emoji, takes two units in a Kotlin string. For such text this loop compares units, not whole symbols. For the plain letters in the lesson it makes no difference.
Complexity
Time: O(n). The pointers start n - 1 apart and close by 2 per iteration, so the loop runs about n / 2 times at most. Each iteration does constant work.
Space: O(1). Two integers are stored, regardless of the string length.
Edge cases and common mistakes
- Empty string.
rightstarts at -1, soleft < rightis false and the function returnstrue. An empty string reads the same in both directions. - One character.
"a"givestrue: both pointers are at index 0, so the loop doesn't run. - Even and odd lengths.
"abba"ends when the pointers cross, and"abcba"ends when they meet onc. Both givetrue. - Using
left <= right. It compares the middle character with itself, which is harmless but unnecessary. - Forgetting to move the pointers. The loop never ends if both pointers stay put on matching characters.
- Returning
trueinside the loop. One matching pair says nothing about the other pairs. Only the mismatch can be decided early. - Case and spaces.
"Aba"and"a b"are not palindromes here, because the code compares exact characters.
Testing
"madam racecar madam"givestrue."abcbx"givesfalse.""givestrue."a"givestrue."ab"givesfalse."Aba"givesfalse.