☕ DSA Java Articles

Topics › Strings › Basic and Easy String Problems

Reverse words in a given string / Palindrome Check

Medium TUF ID 2863 A2Z

Java source ↗ Edit this article ↗

Problem

This sheet row bundles two classic string exercises that share the same tool, a pair of indices moving over a character array. The Java file solves both.

Part A, reverse the words. Given a sentence s made of words separated by spaces, return the words in reverse order joined by single spaces. s may contain leading, trailing or repeated spaces; the result must contain none of those (this is the LeetCode 151 formulation).

Part B, palindrome check. Given a string s, return true if it reads the same forwards and backwards after ignoring every character that is not a letter or digit and ignoring letter case (the LeetCode 125 formulation). The strict version, where every character counts and case matters, is covered in Check if String is Palindrome or Not.

Constraints: 0 ≤ |s| ≤ 2 × 10^5; printable ASCII characters.

Example 1 (Part A)

s = "the sky is blue"
answer = "blue is sky the"

Example 2 (Part A)

s = "  hello   world  "
answer = "world hello"           // extra spaces are dropped

Example 3 (Part B)

s = "A man, a plan, a canal: Panama"
answer = true                    // cleaned: "amanaplanacanalpanama"

Example 4 (Part B)

s = "race a car"
answer = false                   // cleaned: "raceacar", r..r match, then a != c

Approach 1 (Part A): Brute force, split, reverse, join

Intuition. The library already knows how to find words. trim() removes the outer spaces, split("\\s+") cuts on every run of whitespace, so no empty tokens appear in the middle, and reversing the resulting list and joining it with single spaces gives exactly the normalised output.

Algorithm.

  1. parts = s.trim().split("\\s+").
  2. Put the parts in a list and reverse it.
  3. Join with " ".
static String reverseWordsBruteForce(String s) {
    String[] parts = s.trim().split("\\s+");
    List<String> words = new ArrayList<>(Arrays.asList(parts));
    Collections.reverse(words);
    return String.join(" ", words);
}

Complexity. Time O(n): trimming, splitting, reversing and joining are each linear. Space O(n) for the array of words plus the list.

When s is empty or all spaces, trim() yields "", split returns the single element {""}, and String.join returns "", which is the desired answer. This approach is perfectly acceptable in Java; the next one is what an interviewer means by “do it in place”, which matters in languages where strings are mutable.

Approach 2 (Part A): Optimal, squeeze, reverse all, reverse each word

Intuition. Reversing the entire character array puts the words in the right order but spells each word backwards: "the sky" becomes "yks eht". Reversing each word individually fixes the spelling: "sky the". Two reversals, both in place. The only extra work is removing the unwanted spaces first, which is a classic two-index compaction: a read index i walks the input and a write index w marks where the next kept character goes. Because w never overtakes i, writing to a[w] never destroys an unread character.

Algorithm.

  1. Copy s into a char[] a and set w = 0.
  2. Repeat: skip spaces with i; if i reached the end stop; if w > 0 write one separator space; copy the word.
  3. Reverse a[0..w) as a whole.
  4. Walk k from 0 to w; whenever k == w or a[k] == ' ', reverse the word a[start..k) and set start = k + 1.
  5. Return new String(a, 0, w).
static String reverseWordsOptimal(String s) {
    char[] a = s.toCharArray();
    int n = a.length;
    int w = 0;                                          // write index: a[0..w) is the squeezed sentence
    int i = 0;
    while (i < n) {
        while (i < n && a[i] == ' ') i++;               // skip a run of spaces
        if (i == n) break;
        if (w > 0) a[w++] = ' ';                        // one separator before every word except the first
        while (i < n && a[i] != ' ') a[w++] = a[i++];   // copy the word
    }
    reverse(a, 0, w - 1);                               // whole sentence reversed: the words are backwards too
    int start = 0;
    for (int k = 0; k <= w; k++) {
        if (k == w || a[k] == ' ') {                    // a[start..k) is one reversed word
            reverse(a, start, k - 1);
            start = k + 1;
        }
    }
    return new String(a, 0, w);
}

static void reverse(char[] a, int lo, int hi) {
    while (lo < hi) {
        char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
        lo++; hi--;
    }
}

Dry run on s = " hello world ":

step array content (first w chars) w
after squeeze hello world 11
after reversing all dlrow olleh 11
after reversing word 1 (a[0..4]) world olleh 11
after reversing word 2 (a[6..10]) world hello 11

Complexity. Time O(n): the squeeze reads each character once, and each of the two reversal phases swaps at most n/2 pairs. Space O(1) beyond the character array that holds the answer (Java strings are immutable, so one copy is unavoidable).

Why k <= w rather than k < w in the last loop: the final word is not followed by a space, so the sentinel position k == w is treated as a separator to flush it. Without it the last word would stay reversed.

Approach 3 (Part B): Brute force, clean then compare with the reverse

Intuition. Build the string the problem is really asking about: keep only letters and digits, lower-case them, and then apply the textbook palindrome test, “equals its own reverse”.

Algorithm.

  1. Append Character.toLowerCase(c) to a builder for every c that satisfies Character.isLetterOrDigit(c).
  2. Save the forward string, reverse the builder, and compare the two.
static boolean isPalindromeBruteForce(String s) {
    StringBuilder clean = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) clean.append(Character.toLowerCase(c));
    }
    String forward = clean.toString();
    String backward = clean.reverse().toString();
    return forward.equals(backward);
}

Complexity. Time O(n). Space O(n) for the cleaned copy and its reverse.

Note the order: clean.toString() must be taken before clean.reverse(), because reverse() mutates the builder in place.

Approach 4 (Part B): Optimal, two pointers that skip junk

Intuition. A palindrome test only ever compares the k-th character from the left with the k-th from the right. Instead of building the cleaned string, let two indices walk inwards and simply step over anything that is not a letter or digit. The comparison happens on the original string, with both sides lower-cased at the moment of comparison. The first mismatch ends the search, so a non-palindrome is often rejected after a handful of characters.

Algorithm.

  1. lo = 0, hi = n - 1.
  2. While lo < hi: advance lo while it points at a non-alphanumeric; retreat hi likewise.
  3. Compare toLowerCase(s[lo]) with toLowerCase(s[hi]); if different return false.
  4. lo++, hi--. When the pointers meet or cross, return true.
static boolean isPalindromeOptimal(String s) {
    int lo = 0, hi = s.length() - 1;
    while (lo < hi) {
        while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) lo++;
        while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) hi--;
        if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi))) return false;
        lo++;
        hi--;
    }
    return true;
}

Complexity. Time O(n): every character is visited by at most one of the two pointers. Space O(1).

The lo < hi guard inside the two skipping loops matters. On an input like ",,,", without the guard lo would run past the end of the string. With the guard, both pointers meet in the middle, the comparison compares a character with itself, and the method returns true, which is correct because the cleaned string is empty.

Edge cases and pitfalls