Start learning free

LESSON 249 OF 415 · TWO POINTERS

Palindrome Check in Swift: Two Pointers on a Character Array

Practice O(n) Read the full explanation

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 (the two-pointer approach below achieves this).


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • the character at index 0 equals the character at index n - 1
  • the character at index 1 equals the character at index n - 2
  • the character at index 2 equals the character at index 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 through the algorithm?

For as long as i < j:
  • 1. We should check if the characters at indices i and j are different, 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
    Ctrl + Enter to check

    SWIFT · TWO POINTERS

    Palindrome Check in Swift, explained

    Problem overview

    The method isPalindrome receives a string, input, and returns true when it reads the same forwards and backwards. Every character counts, including spaces, and uppercase and lowercase letters are different characters.

    The string "madam racecar madam" is a palindrome. Reversed, it gives the same text, so the answer is true. The string "abcbx" starts with a and ends with x, so the answer is false.

    Approach: compare the ends and walk inward

    You could build the reversed string and compare it with the original. That costs a second copy of the data. The two-pointer idea needs no reversed copy: a palindrome has s[0] == s[n - 1], s[1] == s[n - 2], and so on. So put one pointer, left, at the start and another, right, at the end. Compare the characters they point at, and move both pointers one step toward the middle. If any pair differs, the string isn't a palindrome. If the pointers meet or cross without a mismatch, it is.

    Only half of the characters need to be examined, because each comparison covers two of them. When the length is odd, the middle character has no partner. It only matches itself, so it is never compared.

    Step by step

    The starting code already turns the string into an array of characters, because Swift strings can't be indexed with an integer: input[2] is a compile error. The array chars can be indexed with integers.

    1. Create left as a var starting at 0, the first index. It must be a variable, because it changes in the loop.
    2. Create right as a var starting at chars.count - 1, the last index.
    3. Loop while left < right. While the pointers haven't met, there is a pair left to compare.
    4. Compare the pair. If chars[left] != chars[right], return false at once. One mismatch settles the answer.
    5. Move the pointers. Add 1 to left and subtract 1 from right. Without this, the loop would compare the same pair forever.
    6. Return true after the loop. Every pair matched.

    The solution in Swift

    class Solution {
    func isPalindrome(_ input: String) -> Bool {
        let chars = Array(input)
        var left = 0
        var right = chars.count - 1
        while left < right {
            if chars[left] != chars[right] {
                return false
            }
            left += 1
            right -= 1
        }
        return true
    }
}

    Swift details worth knowing:

    • Array(input) makes a [Character]. A Swift Character is what a reader sees as one character, even when it is built from several Unicode scalars. A letter followed by a combining accent is one Character. Comparing Character values therefore compares what the reader sees. input.count counts Character values too.
    • Why not index the string? Characters have different sizes in memory, so Swift can't jump to the n-th one in constant time. It makes you convert to an array, or step through String.Index values.
    • != works on characters, as on numbers. Nothing like a .equals method is needed.
    • An empty string. Then chars.count - 1 is -1 and left < right is false at once, so the method returns true. Swift's Int can be negative, so no arithmetic goes wrong here.
    • The early return inside the loop leaves the whole method, not just the loop.

    A variant without the array

    To reach the O(1) extra space in the statement, move two String.Index values instead of integers:

    func isPalindromeIndex(_ input: String) -> Bool {
    var left = input.startIndex
    var right = input.endIndex
    while left < right {
        right = input.index(before: right)
        if left == right { break }
        if input[left] != input[right] {
            return false
        }
        left = input.index(after: left)
    }
    return true
}

    endIndex points one past the last character, so right is moved back before each comparison. The left == right check stops the loop when both indices meet on the middle character of an odd-length string. It returns the same answers as the lesson's version for "abba", "aba", "abcbx" and the empty string.

    Complexity

    Time: O(n). Building the array takes one pass, and the loop makes at most n / 2 comparisons.

    Space: O(n) in this version. Array(input) copies the characters. The two pointers add only O(1). The statement asks for O(1) extra space, which a string-index version could reach by moving two String.Index values toward each other, but that is harder to read. This lesson trades the extra memory for simple integer indexing.

    Edge cases and common mistakes

    • Empty string and one character. Both are palindromes. For "" and "a" the loop never runs and the method returns true.
    • Odd and even lengths. "abba" ends with left equal to 2 and right equal to 1, and "aba" ends with both at 1. Both stop correctly.
    • Case and spaces matter. "Madam" returns false because M and m differ. "race car" returns false because its spaces are compared like other characters, so the first r meets the last r, then a meets a, and then c meets the space.
    • Using <= instead of <. On an odd-length string the pointers land on the same middle character, which compares equal to itself, so the result is the same. The extra comparison is useless, and < says what is meant: compare pairs.
    • Forgetting to move a pointer. If only one pointer moves, the comparisons are wrong, and if neither moves, the loop never ends.
    • Writing input[i]. It doesn't compile. Use the chars array.

    Testing

    • "madam racecar madam" gives true.
    • "abcbx" gives false.
    • "" gives true.
    • "a" gives true.
    • "abba" gives true.
    • "Madam" gives false.
    • "race car" gives false.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free