Palindrome String

Q: How do you check if a string is a palindrome?

Compare the first character with the last, the second with the second to last, and so on toward the middle. If any pair differs, the string is not a palindrome. Two indexes that start at both ends and move inward do this in one pass.

Q: Can you check a palindrome without extra memory?

Yes. The two pointer check reads the characters in place and stores two indexes, so it uses O(1) extra space. Comparing s with its reverse is shorter to write but builds a second string of n characters.

Q: What is the time complexity of checking a palindrome string?

O(n) for a string of length n . The two pointer check makes at most n / 2 comparisons and stops at the first mismatch, so coddy takes one comparison.

Q: Is a single character a palindrome?

Yes, it reads the same in both directions. In the two pointer loop left and right both start at index 0, the loop never runs, and the function returns true .

BeginnerTwo pointers Arrays and strings

+10

A string is a palindrome when it reads the same from left to right as from right to left, like level. Write a function that gets a string s of lowercase English letters and returns true if s is a palindrome and false otherwise.

Function

isPalindrome(s: string) → boolean

sstring: the lowercase string to check
Returnsboolean: true when s reads the same in both directions

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s contains only lowercase English letters (a to z).

Examples

Input: s = "racecar"
Output: true
Explanation: Compare from the outside in: r with r, a with a, c with c. The middle e has no partner and needs none, so the answer is true.

Input: s = "abba"
Output: true
Explanation: With an even length every letter has a partner: the two as match and the two bs match, so the answer is true.

Input: s = "coddy"
Output: false
Explanation: The first letter c and the last letter y already differ, so coddy is not a palindrome and the answer is false.

Follow-up

How would you change the two pointers to skip spaces and punctuation and ignore case, so that Was it a car or a cat I saw counts as a palindrome?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A palindrome equals its own reverse, so you can build the reverse and compare. You do not need the copy: the first character must match the last, the second the second to last, and so on. Two indexes walking inward test those pairs in place and stop at the first mismatch.

Compare the string with its reverse

Intuition

Reverse s and compare: racecar reversed is racecar, and coddy reversed is yddoc. A string reads the same both ways exactly when it equals its reverse.

The time is O(n), but the reversed copy is O(n) extra space, 50,000 characters at n = 5 × 10^4. The work is also always full: coddy is decided by its first and last letters, yet all five get reversed first.

Algorithm

Build the reverse of s, with the language's reverse function or a loop from the last character to the first.
Compare the reverse with s.
Return true if they are equal and false otherwise.

def isPalindrome(s):
    return s == s[::-1]

Two pointers from both ends

Intuition

Reversing moves index i to index n-1-i, so s equals its reverse exactly when s[i] equals s[n-1-i] for every i. Each pair appears twice in that condition, so checking the left half is enough. In racecar the pairs are (0, 6), (1, 5) and (2, 4); the middle e at index 3 needs no partner.

The first pair that differs proves the answer is false, so coddy is decided after one comparison. At most n / 2 comparisons run, O(n) time, and two indexes are O(1) space. R first reads the string as a vector of character codes, which costs O(n).

Algorithm

Set left = 0 and right = n-1.
While left < right, compare s[left] with s[right].
If they differ, return false.
Otherwise add 1 to left, subtract 1 from right and repeat.
When the pointers meet or cross, every pair matched: return true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Pitfalls and edge cases

Returning true as soon as one pair matches. abca passes its outer pair and fails the inner one, so true comes only after the loop.
Starting right at n instead of n-1, which reads past the end (in C, the terminating '\0'). In Lua and R indexes run from 1 to n, so there right does start at n.
Comparing strings with == in C. reversed == s compares two pointers and is false for a copy; use strcmp.
Building the reverse with result = result + ch. Each step copies the string so far: about 1.25 × 10^9 character copies for 50,000 letters.
Indexing a Swift string with an integer: it does not compile. Walk s.utf8 or copy the characters into an array.

Frequently asked questions4

How do you check if a string is a palindrome?

Compare the first character with the last, the second with the second to last, and so on toward the middle. If any pair differs, the string is not a palindrome. Two indexes that start at both ends and move inward do this in one pass.

Can you check a palindrome without extra memory?

Yes. The two pointer check reads the characters in place and stores two indexes, so it uses O(1) extra space. Comparing s with its reverse is shorter to write but builds a second string of n characters.

What is the time complexity of checking a palindrome string?

O(n) for a string of length n. The two pointer check makes at most n / 2 comparisons and stops at the first mismatch, so coddy takes one comparison.

Is a single character a palindrome?

Yes, it reads the same in both directions. In the two pointer loop left and right both start at index 0, the loop never runs, and the function returns true.

def isPalindrome(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "racecar"

Expected Output

true