Start learning free

LESSON 173 OF 348 · STRINGS

Palindrome Check in Kotlin: Compare with the Reversed String

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.


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 2
    Ctrl + Enter to check

    KOTLIN · STRINGS

    Palindrome Check in Kotlin, explained

    Problem overview

    The function isPalindrome receives a string, input, and returns true when it reads the same forwards and backwards, and false otherwise. Spaces count as characters like any other. In the first example, "madam racecar madam" reversed is again "madam racecar madam", so the answer is true. For "abcbx" the reverse is "xbcba", which differs, so the answer is false.

    The statement's note asks for O(n) time and O(1) extra space, and its hints describe two pointers that walk toward the middle. This lesson solves the same problem a shorter way and trades the space guarantee for simplicity.

    Approach: reverse, then compare

    The definition of a palindrome is already an algorithm: build the reversed string and check whether it equals the original. Kotlin gives you both halves ready-made. reversed() produces the reversed text, and == compares two strings by content.

    The two-pointer method from the statement's hints checks pairs from the outside in, starting with input[0] against input[n - 1], and uses no extra memory. This lesson's version allocates a second string the same length as the input, so its space use is O(n), not O(1). The time is still linear, and the code is two lines. Once this makes sense, the two-pointer solution is the natural next step.

    Step by step

    1. Reverse the input. input.reversed() returns a new string with the characters in the opposite order and stores it in the val named reversedInput. The original input doesn't change, because strings in Kotlin never change in place.
    2. Compare and return. input == reversedInput is already a Boolean, true exactly when the two strings hold the same characters in the same order. Returning it directly replaces an if that would return true or false.

    The solution in Kotlin

    class Solution {
    fun isPalindrome(input: String): Boolean {
        val reversedInput = input.reversed()
        return input == reversedInput
    }
}

    Kotlin details worth knowing:

    • == compares contents. In Kotlin, == calls equals, so two different string objects with the same characters are equal. The operator === compares references and would give false here for a palindrome that was built separately. Always use == for strings.
    • reversed() on a String returns a String. The same name exists on lists, where it also returns a new list. The in-place version for a mutable list is reverse(), without the d.
    • Case counts. The comparison is case-sensitive, so "Aba" is not a palindrome: its reverse is "abA".
    • Surrogate pairs. String.reversed() keeps a surrogate pair, such as an emoji, in the right order, so emoji strings are handled correctly.
    • Inline form. The function could also be written as fun isPalindrome(input: String): Boolean = input == input.reversed(). The two-line version is kept here so each step has a name.

    Complexity

    Time: O(n). Reversing visits each of the n characters once, and the comparison looks at up to n characters, stopping at the first difference.

    Space: O(n). reversed() allocates a second string of the same length. The two-pointer approach in the statement's hints reaches O(1) because it compares characters in place, using only two indexes.

    Edge cases and common mistakes

    • Empty string. "" reversed is "", so the function returns true. An empty sequence reads the same both ways.
    • Single character. Any one-character string is a palindrome.
    • Spaces are characters. "race car" reversed is "rac ecar", so it is not a palindrome here, even though the letters alone are. Skipping spaces or ignoring case would be a different problem.
    • Uppercase and lowercase differ. "Aba" returns false, as explained above.
    • Using ===. It compares references and gives unreliable answers for strings. Use ==.
    • Expecting the input to change. input.reversed() doesn't modify input. Nothing is reversed unless you keep the returned value.

    Testing

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