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; if every pair matches, it is. 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 only 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?

It is 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 a string whose first and last characters differ is decided after one comparison.

Q: Is a single character a palindrome?

Yes. One character reads the same in both directions, so the answer is true . 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.

+16 hidden tests on Submit

Follow-up

A sentence such as Was it a car or a cat I saw is a palindrome once you ignore case, spaces and punctuation. How would you change the two pointers to skip those characters?

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 the direct check builds the reverse and compares. The better check builds nothing: the first character has to match the last, the second the second to last, and so on toward the middle. Two indexes walking inward test those pairs in place and stop at the first mismatch.

Compare the string with its reverse

Intuition

Reading s the same in both directions means s equals its reverse. So reverse it and compare: racecar reversed is racecar, and coddy reversed is yddoc, which differs.

Building the reverse and comparing each touch every character once, so the time is O(n). The reversed copy holds n more characters, which is O(n) extra space: at n = 5 × 10^4 that is 50,000 characters built only to be compared and thrown away.

It also does the full work every time. coddy is decided by its first and last letters, yet this approach reverses all five before it looks.

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 the character at 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 shows up twice in that list, so check only the left half. Put left at index 0 and right at index n-1, compare the two characters, and move both pointers one step inward.

Stop when the pointers meet or cross. In racecar they check the index pairs (0, 6), (1, 5) and (2, 4), then meet on index 3, the middle e, which needs no partner. In abba they check (0, 3) and (1, 2) and then cross. The first pair that differs proves the answer is false, so you return at once: coddy is decided after one comparison.

At most n / 2 comparisons happen, which is O(n) time, and the only memory is two indexes, O(1) space. R is the exception: it reads the string as a vector of character codes first, 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

The loop is short, so the mistakes sit in its bounds and its return statements.

Returning true as soon as one pair matches. abca passes its outer pair and fails on the inner one, so true may only come after the loop ends.
Starting right at n instead of n-1, which reads past the end (in C, the terminating '\0'). In Lua and R the indexes run from 1 to n, so there right starts at n.
Comparing strings by address. In C, reversed == s compares two pointers and is always false for a fresh copy; use strcmp.
Building the reverse with result = result + ch in a loop. Each step copies the whole 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 with its own indexes 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; if every pair matches, it is. 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 only 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?

It is 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 a string whose first and last characters differ is decided after one comparison.

Is a single character a palindrome?

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

Python

def isPalindrome(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "racecar"

Expected

true