LESSON 223 OF 338 · TWO POINTERS

Palindrome Check in Go: Two Pointers, O(n) Time and O(1) Space

Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward

Example 1:

Input:  "madam racecar madam"

Output: true

Example 2:

Input:  "abcbx"

Output: false

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:

s[0] == s[n - 1]
s[1] == s[n - 2]
s[2] == s[n - 3]
...

How can we check all these pairs of corresponding characters while traversing the string one time?

We can use two pointers! One index variable i starting from the beginning (i = 0) and one index variable j starting from the end of the string (j = n - 1). How should we move these pointers throught the algorithm?

For as long as i < j:

1. We should check if s[i] != s[j] and if so, we conclude the string is not a palindrome and return false.
2. Move i one step to the right.
3. Move j one step to the left.
4. Go to step 1.

If i became greater than or equal to j and we haven't returned false, then we can conclude the string is a palindrome and return true.

STEP 1 OF 6

Guided

Ctrl + Enter to check

Palindrome Check in Go, explained

Problem overview

The function isPalindrome receives a string, input, and returns true when it reads the same backward as forward. The comparison is exact: every character counts, including spaces, and upper and lower case letters are different characters.

For "madam racecar madam" the answer is true: the first and last characters match, then the second and second-to-last, and so on toward the middle. For "abcbx" the answer is false, because a and x already differ. The statement asks for O(n) time and O(1) extra space.

Approach: compare from both ends

The obvious way is to build a reversed copy of the string and compare it with the original. That works in O(n) time, but the copy takes O(n) extra space, which breaks the budget.

A palindrome has a simple structure: input[0] equals input[n-1], input[1] equals input[n-2], and so on. So there is no need for a copy. Keep two indices, left at the start and right at the end, compare the characters they point to, and move both toward the middle. One mismatch proves the string is not a palindrome. If the pointers meet or cross without a mismatch, every pair matched.

The middle character of an odd-length string is never compared, and that is fine, because it is its own mirror image. An empty string and a one-character string are palindromes: the loop doesn't run, and the function returns true.

Step by step

Create left as a variable starting at 0. Both pointers change inside the loop, so they must be variables.
Create right starting at len(input) - 1, the last index, because indices start at 0.
Loop while left < right. Go has no while, so this is a for with only a condition. When the pointers meet, no pair is left to compare.
Return false on a mismatch. One unequal pair is enough to decide.
Move both pointers inward with left++ and right--. Without this, the loop would compare the same pair forever.
Return true after the loop. The code reaches this line only if every pair matched.

The solution in Go

func isPalindrome(input string) bool {
    left := 0
    right := len(input) - 1
    for left < right {
        if input[left] != input[right] {
            return false
        }
        left++
        right--
    }
    return true
}

The Go details worth a closer look:

Indexing gives a byte. A Go string is a sequence of bytes, so input[left] has type byte (an alias for uint8), not a character. For plain ASCII text, one byte is one character and the code is correct. For text with accented letters or other non-ASCII characters, a character can take several bytes, and the code compares bytes. For example, "été" is a palindrome as text but has the bytes 195 169 116 195 169, and the function returns false for it. Handling such text means converting to []rune first.
len counts bytes too. len(input) is the number of bytes, which equals the number of characters only for ASCII.
Comparing bytes with !=. Both sides have the same type, so the comparison compiles and works as expected. Comparing a byte with a string such as "a" would be a type error; a character literal like 'a' is the right form for a byte.
No extra memory. Reading input[i] copies nothing, and strings are immutable, so the function can't change its argument by accident.
Empty input is safe. For "", right is -1 and left < right is false, so the loop is skipped and no indexing happens.

Complexity

Time: O(n). Each iteration moves the pointers closer by two positions, so the loop runs at most n / 2 times, with constant work per iteration.

Space: O(1). Only left and right are stored.

Edge cases and common mistakes

Empty string and one character. Both return true.
Even length. "abba" gives true and "ab" gives false. The pointers cross instead of meeting on a character, and the condition left < right handles that.
Case and spaces. "Aba" gives false, since A and a are different bytes. Spaces are characters like any other.
Using left <= right. It compares the middle character with itself. That is harmless, but it does extra work.
Forgetting to move the pointers. The loop never ends.
Stopping at the first match. Returning true inside the loop after one matching pair would accept "abcda", whose first and last characters match. Only a mismatch can decide early.

Testing

"madam racecar madam" gives true.
"abcbx" gives false.
"" and "a" give true.
"ab" gives false, and "abba" gives true.
"Aba" gives false.

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free