30 Java String Programs for Interviews (Brute Force to Optimal)

The brute version appends in a loop, which copies the growing string each time: O(n²). StringBuilder.reverse() is O(n). JIT or javac does not fix the loop version, as the timing at the bottom of this post shows: 634 ms against 1 ms on 50,000 characters.

// brute
String r = "";
for (int i = s.length() - 1; i >= 0; i--) r += s.charAt(i);
// optimal
new StringBuilder(s).reverse().toString()
// stream
IntStream.range(0, s.length()).mapToObj(i -> String.valueOf(s.charAt(s.length() - 1 - i))).collect(Collectors.joining())

P01 reverse hello -> brute=olleh | optimal=olleh | stream=olleh | same=true

Source: StringInterviewPrograms.java, reverseBrute, reverseOpt, reverseStream

Brute: compare with the reversed string (O(n) time, O(n) extra memory). Optimal: two pointers walking inwards, O(1) extra memory. The follow-up is always punctuation and case: clean first with toLowerCase().replaceAll("[^a-z0-9]", ""). The second output line shows the same sentence failing raw and passing once cleaned.

// brute
s.equals(new StringBuilder(s).reverse().toString())
// optimal
int i = 0, j = s.length() - 1;
while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
return true;
// stream
IntStream.range(0, s.length() / 2).allMatch(i -> s.charAt(i) == s.charAt(s.length() - 1 - i))

P02 palindrome racecar -> brute=true | optimal=true | stream=true | same=true
P02 palindrome 'A man, a plan, a canal: Panama' raw / cleaned first -> false / true

Source: StringInterviewPrograms.java, palBrute, palOpt, palStream, clean

Count letters only, so spaces and digits are neither. The brute version calls indexOf on a vowel string for every letter, the optimal one uses a switch. Both are O(n); the difference is a constant factor, not a complexity class.

// brute
if (Character.isLetter(ch)) { if ("aeiouAEIOU".indexOf(ch) >= 0) v++; else c++; }
// optimal
switch (Character.toLowerCase(ch)) { case 'a', 'e', 'i', 'o', 'u' -> v++; default -> c++; }
// stream
long v = s.chars().filter(ch -> "aeiouAEIOU".indexOf(ch) >= 0).count();
long c = s.chars().filter(Character::isLetter).count() - v;

P03 vowels/consonants in 'Hello World Java' -> brute=5/9 | optimal=5/9 | stream=5/9 | same=true

Source: StringInterviewPrograms.java, vcBrute, vcOpt, vcStream

The brute version uses a TreeMap with containsKey then put (two lookups, O(log k) each). An int[128] counting array is O(n) with no hashing, but it assumes ASCII; for arbitrary text use a Map or int[65536]. I used TreeMap so the printed order is stable.

// optimal (ASCII)
int[] cnt = new int[128];
for (char c : s.toCharArray()) cnt++;
// stream
s.chars().mapToObj(c -> (char) c).collect(Collectors.groupingBy(Function.identity(), TreeMap::new,
        Collectors.collectingAndThen(Collectors.counting(), Long::intValue)))

P04 char frequency mississippi -> brute={i=4, m=1, p=2, s=4} | optimal={i=4, m=1, p=2, s=4} | stream={i=4, m=1, p=2, s=4} | same=true

Source: StringInterviewPrograms.java, freqBrute, freqOpt, freqStream

Brute: for each character scan the whole string for another copy, O(n²). Optimal: one pass to count, one pass to find the first count of 1, O(n). The stream version needs a LinkedHashMap so the entries stay in first-seen order.

// optimal
int[] c = new int[65536];
for (char ch : s.toCharArray()) c[ch]++;
for (char ch : s.toCharArray()) if (c[ch] == 1) return ch;
return null;

P05 first non-repeated char in stress -> brute=t | optimal=t | stream=t | same=true

Source: StringInterviewPrograms.java, fnrBrute, fnrOpt, fnrStream

“First repeated” means the first character you reach that you have already seen. Brute: for each position, search the prefix before it with indexOf, O(n²). Optimal: a HashSet, where add returning false is the signal, O(n). I did not write a stream version: it would need a stateful lambda, and that is a code smell (see Q6 in the stream questions).

// brute
for (int j = 1; j < s.length(); j++) if (s.substring(0, j).indexOf(s.charAt(j)) >= 0) return s.charAt(j);
// optimal
Set<Character> seen = new HashSet<>();
for (char c : s.toCharArray()) if (!seen.add(c)) return c;

P06 first repeated char in programming -> brute=r | optimal=r | same=true

Source: StringInterviewPrograms.java, frBrute, frOpt

Brute: before appending a character, search the result so far with indexOf, O(n·k) where k is the number of distinct characters. Optimal: a LinkedHashSet keeps insertion order and gives O(n). The stream version is chars().distinct().

// stream
s.chars().distinct().mapToObj(c -> String.valueOf((char) c)).collect(Collectors.joining())

P07 remove duplicate chars banana -> brute=ban | optimal=ban | stream=ban | same=true

Source: StringInterviewPrograms.java, dedupBrute, dedupOpt, dedupStream

Sort both and compare: O(n log n). Counting letters with an int[26], incrementing for one string and decrementing for the other, is O(n), but it assumes lowercase a to z; say that assumption out loud. Check the lengths first, because different lengths can never be anagrams.

// optimal (lowercase a-z)
int[] cnt = new int[26];
for (int i = 0; i < a.length(); i++) { cnt[a.charAt(i) - 'a']++; cnt[b.charAt(i) - 'a']--; }
for (int c : cnt) if (c != 0) return false;
return true;

P08 anagram listen/silent -> brute=true | optimal=true | stream=true | same=true
P08 anagram hello/world -> brute=false | optimal=false | stream=false | same=true

Source: StringInterviewPrograms.java, anaSort, anaCount, anaStream

The brute version splits on a single space and concatenates backwards. The optimal one trims, splits on \s+ so runs of spaces collapse, reverses the list and joins. Interviewers ask about the extra spaces, which is why the trim and the regex are there.

// optimal
List<String> l = Arrays.asList(s.trim().split("\\s+"));
Collections.reverse(l);
String.join(" ", l)
// stream
String[] w = s.trim().split("\\s+");
IntStream.range(0, w.length).mapToObj(i -> w[w.length - 1 - i]).collect(Collectors.joining(" "))

P09 reverse words 'java is fun' -> brute=fun is java | optimal=fun is java | stream=fun is java | same=true

Source: StringInterviewPrograms.java, revWordsBrute, revWordsOpt, revWordsStream

The optimal version works in place on a char[]: find each word boundary and swap characters inwards, with no extra strings created per word.

char[] a = s.toCharArray();
int start = 0;
for (int i = 0; i <= a.length; i++) {
    if (i == a.length || a[i] == ' ') {
        for (int l = start, r = i - 1; l < r; l++, r--) { char t = a[l]; a[l] = a[r]; a[r] = t; }
        start = i + 1;
    }
}
return new String(a);

P10 reverse each word 'java is fun' -> brute=avaj si nuf | optimal=avaj si nuf | stream=avaj si nuf | same=true

Source: StringInterviewPrograms.java, revEachBrute, revEachOpt, revEachStream

Brute: sort the words by length descending and take the first, O(w log w). Optimal: one scan keeping the best so far, O(n). Stream: max(Comparator.comparingInt(String::length)). The scan uses >, so on a tie the first word wins.

String best = "";
for (String w : s.split(" ")) if (w.length() > best.length()) best = w;
return best;

P11 longest word -> brute=brownish | optimal=brownish | stream=brownish | same=true

Source: StringInterviewPrograms.java, longestBrute, longestOpt, longestStream

The input here is " hello world java ": three words, padded with spaces. split(" ") returns 8 elements because every extra space makes an empty string (the single trailing space is dropped, because split removes trailing empties). The correct answer is trim().split("\\s+"). And there is a second trap in that fix: on an all-blank string, trim() gives "" and "".split("\\s+") returns one empty string, so the count is 1. Guard with isBlank().

ws.split(" ").length
ws.trim().split("\\s+").length
Arrays.stream(ws.split("\\s+")).filter(w -> !w.isEmpty()).count()
"   ".isBlank() ? 0 : "   ".trim().split("\\s+").length

P12 word count: split(" ") / trim().split("\\s+") / stream filter -> 8 / 3 / 3
P12 blank string '   ' word count: trim().split("\\s+") / guarded -> 1 / 0

Source: StringInterviewPrograms.java, main, section P12

A pangram uses every letter a to z. Brute: for each of the 26 letters call indexOf, O(26·n). Optimal: one pass with a boolean[26] and a counter that returns as soon as it reaches 26. The stream filters to a to z first, so letters like é are not counted towards the 26.

boolean[] seen = new boolean[26];
int count = 0;
for (char c : s.toLowerCase().toCharArray()) {
    if (c >= 'a' && c <= 'z' && !seen) { seen = true; if (++count == 26) return true; }
}
return false;

P13 pangram -> brute=true | optimal=true | stream=true | same=true
P13 pangram 'hello world' -> brute=false | optimal=false | stream=false | same=true

Source: StringInterviewPrograms.java, pangramBrute, pangramOpt, pangramStream

Brute: build each of the n rotations and compare, O(n²). Optimal: b is a rotation of a exactly when it has the same length and appears inside a + a. Always check the lengths first, otherwise "abc" would be a “rotation” of "bc". The stream column here is just anyMatch over the rotation indexes.

a.length() == b.length() && (a + a).contains(b)

P14 rotation waterbottle/erbottlewat -> brute=true | optimal=true | stream=true | same=true
P14 rotation abcd/acbd -> brute=false | optimal=false | same=true

Source: StringInterviewPrograms.java, rotBrute, rotOpt

Brute: test every substring with a palindrome check, O(n³). Optimal: expand around every centre, odd and even, O(n²) with O(1) space (the figure above). Both keep the earlier one on a tie, which is why babad gives bab and not aba. On a 600-character string the brute force took 34 ms against 4 ms for the centre expansion; it is a single run on a small input, so read it as the direction of the gap, not a benchmark.

int start = 0, len = 0, n = s.length();
for (int c = 0; c < n; c++) {
    for (int odd = 0; odd < 2; odd++) {
        int l = c, r = c + odd;
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { l--; r++; }
        int cur = r - l - 1;
        if (cur > len) { len = cur; start = l + 1; }
    }
}
return s.substring(start, start + len);

P15 longest palindromic substring of babad -> brute=bab | optimal=bab | same=true
P15 longest palindromic substring of cbbd -> brute=bb | optimal=bb | same=true
BENCH longest palindromic substring of a 600-char string: brute 34 ms, expand-around-center 4 ms, same answer true

Source: StringInterviewPrograms.java, lpsBrute, lpsOpt

Brute: from each start, extend until a repeat, O(n²). Optimal: a sliding window with a map from character to its last index. When the current character was last seen inside the window, move the left edge to just after that position, so no character is ever visited twice. The check prev >= left matters: without it the window jumps backwards on stale entries.

Map<Character, Integer> last = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    Integer prev = last.get(c);
    if (prev != null && prev >= left) left = prev + 1;
    last.put(c, right);
    best = Math.max(best, right - left + 1);
}
return best;

P16 longest substring without repeats abcabcbb -> brute=3 | optimal=3 | same=true
P16 longest substring without repeats pwwkew -> brute=3 | optimal=3 | same=true

Source: StringInterviewPrograms.java, lswBrute, lswOpt

Three honest answers with no real complexity gap: shrink a prefix until every string starts with it; sort the array and compare only the first and last (they are the two most different); or reduce pairwise. All are bounded by the total number of characters (the sort approach adds the sort cost). Pick the one you can explain.

// sort, then compare first and last
String[] c = w.clone();
Arrays.sort(c);
return common(c[0], c);
// stream
Arrays.stream(w).reduce(StringInterviewPrograms::common).get()

P17 longest common prefix -> brute=fl | optimal=fl | stream=fl | same=true

Source: StringInterviewPrograms.java, lcpBrute, lcpOpt, lcpStream, common

Brute: keep deleting (), [], {} pairs until nothing changes; it works but is O(n²). Optimal: a stack. On each opener push the closer you expect; on a closer pop and compare. The string is valid only if the stack is empty at the end, which is what rejects ((.

Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    switch (c) {
        case '(' -> st.push(')');
        case '[' -> st.push(']');
        case '{' -> st.push('}');
        default -> { if (st.isEmpty() || st.pop() != c) return false; }
    }
}
return st.isEmpty();

P18 valid parentheses [{[()]}, ([)], ((] -> brute=[true, false, false] | optimal=[true, false, false] | same=true

Source: StringInterviewPrograms.java, parenBrute, parenOpt

The brute version builds the result with r = r + ..., which is quadratic for long runs of distinct characters; the optimal one uses a StringBuilder. This is also where the stream temptation bites: groupingBy counts every occurrence of a character, not each consecutive run. On aabaa the correct encoding is a2b1a2 but the stream gives a4b1, which cannot be decoded back. Run-length encoding is order-dependent and needs a loop.

StringBuilder sb = new StringBuilder();
int i = 0;
while (i < s.length()) {
    int j = i;
    while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
    sb.append(s.charAt(i)).append(j - i);
    i = j;
}
return sb.toString();

P19 run-length encode aaabbbccd -> brute=a3b3c2d1 | optimal=a3b3c2d1 | same=true
P19 stream groupingBy trap on aabaa: correct RLE / groupingBy -> a2b1a2 / a4b1

Source: StringInterviewPrograms.java, rleBrute, rleOpt, rleWrongStream

Two strings are isomorphic if one can be turned into the other by a consistent one-to-one letter mapping. The subtle part is “one-to-one”: badc and baba fail because b and d would both have to map to b, so you need maps in both directions. The brute alternative compares “first-occurrence signatures” of each string. Both are O(n).

Map<Character, Character> ab = new HashMap<>(), ba = new HashMap<>();
for (int i = 0; i < a.length(); i++) {
    char x = a.charAt(i), y = b.charAt(i);
    if (ab.putIfAbsent(x, y) != null && ab.get(x) != y) return false;
    if (ba.putIfAbsent(y, x) != null && ba.get(y) != x) return false;
}
return true;

P20 isomorphic egg/add, foo/bar, paper/title, badc/baba -> brute=[true, false, true, false] | optimal=[true, false, true, false] | same=true

Source: StringInterviewPrograms.java, isoBrute, isoOpt, signature

There are n! permutations, so the work is at least O(n·n!) however you write it; the only difference between the two versions is copying. The brute version builds a new prefix and remainder string at each step. The optimal one swaps characters in a char[] and swaps back (backtracking). With repeated letters you get duplicates: aab generates 6 results but only 3 are distinct. There is no stream version; recursion is the point.

static void swapPerm(char[] a, int k, List<String> out) {
    if (k == a.length) { out.add(new String(a)); return; }
    for (int i = k; i < a.length; i++) {
        char t = a[k]; a[k] = a[i]; a[i] = t;
        swapPerm(a, k + 1, out);
        t = a[k]; a[k] = a[i]; a[i] = t;
    }
}

P21 permutations of abc -> brute=[abc, acb, bac, bca, cab, cba] | optimal=[abc, acb, bac, bca, cab, cba] | same=true
P21 permutations of aab: generated / unique -> 6 / 3 [aab, aba, baa]

Source: StringInterviewPrograms.java, permute, swapPerm

A string of length n has n(n+1)/2 substrings, 10 for abab, but only 7 are distinct. The straightforward answer puts every substring into a Set: O(n²) substrings, each hashed in O(n), so O(n³). A linear-time answer exists (a suffix automaton or suffix array), but it is not an interview-length program and I have not implemented it here.

IntStream.range(0, ss.length()).boxed()
    .flatMap(i -> IntStream.rangeClosed(i + 1, ss.length()).mapToObj(j -> ss.substring(i, j)))
    .distinct().count()

P22 substrings of abab: all / distinct set / distinct stream -> 10 / 7 [a, ab, aba, abab, b, ba, bab] / 7

Source: StringInterviewPrograms.java, substrings, main section P22

The bit trick: in ASCII, upper and lower case letters differ by exactly bit 5 (value 32), so c ^ 32 flips the case. It is fast but only valid for ASCII letters, so the code guards with a range check. The brute and stream versions use Character.isUpperCase, which handles other alphabets too.

if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) a[i] = (char) (c ^ 32);

P23 toggle case 'Hello World 123' -> brute=hELLO wORLD 123 | optimal=hELLO wORLD 123 | stream=hELLO wORLD 123 | same=true

Source: StringInterviewPrograms.java, toggleBrute, toggleOpt, toggleStream

Two common answers that agree on ASCII and disagree elsewhere. replaceAll("[^A-Za-z0-9]", "") removes every non-ASCII letter. Character::isLetterOrDigit keeps them. On café 1! (with an accented e) the regex gives 4 characters and the stream gives 5, and only the stream keeps the accented letter. Neither is wrong; decide what “alphanumeric” means for your data.

plain.replaceAll("[^A-Za-z0-9]", "")
plain.chars().filter(Character::isLetterOrDigit)
     .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)

P24 strip non-alphanumerics from 'a1 b2, c3!': regex / isLetterOrDigit -> a1b2c3 / a1b2c3
P24 same on 'caf' + e-acute + ' 1!': regex length / isLetterOrDigit length / e-acute kept by each -> 4 / 5 / false , true

Source: StringInterviewPrograms.java, main section P24

First decide whether overlaps count. In aaaa, the substring aa occurs 2 times without overlap and 3 times with. The difference between the two loops is one line: advance the search index by the pattern length, or by 1. The “replace and compare lengths” one-liner always counts without overlap.

// non-overlapping: i += sub.length();   overlapping: i++;
while ((i = s.indexOf(sub, i)) >= 0) { n++; i += sub.length(); }
// replace trick (non-overlapping)
(s.length() - s.replace(sub, "").length()) / sub.length()
// overlapping, stream
IntStream.range(0, s.length() - sub.length() + 1).filter(i -> s.startsWith(sub, i)).count()

P25 count 'aa' in 'aaaa': non-overlapping / replace trick / overlapping / overlapping stream -> 2 / 2 / 3 / 3

Source: StringInterviewPrograms.java, countNonOverlap, countOverlap

An old puzzle. Concatenate into a, take b back out of the front, then take a out of the back. It works because strings are immutable values and the variables are just references, but in real code a temp variable is clearer and costs nothing. Note it allocates new strings, so it is not even cheaper.

a = a + b;
b = a.substring(0, a.length() - b.length());
a = a.substring(b.length());

P26 swap 'hello' and 'world' without a temp variable -> a=world, b=hello

Source: StringInterviewPrograms.java, main section P26

Three answers, three behaviours. The stream allMatch(Character::isDigit) returns true for the empty string (vacuous truth) and for Arabic-Indic digits. The regex \d+ rejects the empty string and, by default, anything but 0 to 9. A plain ASCII loop with an empty check does the same as the regex. For input validation, the loop or regex is almost always what you want.

s.matches("\\d+")
s.chars().allMatch(Character::isDigit)
// ascii loop
if (s.isEmpty()) return false;
for (char c : s.toCharArray()) if (c < '0' || c > '9') return false;
return true;

P27 digits only? 12345 : regex \d+ / allMatch(isDigit) / ascii loop -> true / true / true
P27 digits only? 12a45 : regex \d+ / allMatch(isDigit) / ascii loop -> false / false / false
P27 digits only? empty : regex \d+ / allMatch(isDigit) / ascii loop -> false / true / false
P27 digits only? arabic-indic : regex \d+ / allMatch(isDigit) / ascii loop -> false / true / false

Source: StringInterviewPrograms.java, digitsAscii, main section P27

Brute: a flag marks “start of word” and the loop upper-cases the next letter. The split version upper-cases the first letter and lower-cases the rest. Splitting with limit -1 keeps empty strings, so double spaces survive instead of crashing on charAt(0) of an empty word. This simple version treats only a space as a separator.

Arrays.stream(s.split(" ", -1))
    .map(w -> w.isEmpty() ? w : Character.toUpperCase(w.charAt(0)) + w.substring(1).toLowerCase())
    .collect(Collectors.joining(" "))

P28 title case -> brute=Hello World From Java | optimal=Hello World From Java | stream=Hello World From Java | same=true

Source: StringInterviewPrograms.java, titleBrute, titleOpt, titleStream

The interview version asks you to skip leading spaces, read an optional sign, read digits until something else appears, and clamp on overflow. The key is accumulating in a long and checking the bounds on every digit, so you stop before it can overflow. Compare with Integer.parseInt, which throws on the same input; that is the right behaviour for validation, and atoi is the right one for lenient parsing.

long v = 0;
while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
    v = v * 10 + (s.charAt(i) - '0');
    if (sign * v > Integer.MAX_VALUE) return Integer.MAX_VALUE;
    if (sign * v < Integer.MIN_VALUE) return Integer.MIN_VALUE;
    i++;
}
return (int) (sign * v);

P29 atoi('  -42abc') -> -42
P29 atoi('4193 with words') -> 4193
P29 atoi('words 987') -> 0
P29 atoi('2147483648') -> 2147483647
P29 atoi('-91283472332') -> -2147483648
P29 Integer.parseInt('  -42abc') -> NumberFormatException: For input string: "  -42abc"

Source: StringInterviewPrograms.java, atoi

This is the question that separates people who know how Java stores text. A String is a sequence of UTF-16 units, and an emoji outside the Basic Multilingual Plane takes two (a surrogate pair). The test string is a, a grinning-face emoji, b: length() says 4 but there are 3 code points. A char-by-char reverse puts the pair backwards (DE00 D83D), which is not a valid character anymore. StringBuilder.reverse() is documented to treat surrogate pairs as one unit and gets it right. Reversing over codePoints() by hand does as well. The output is shown as hexadecimal UTF-16 units so it does not depend on your terminal’s font.

int[] cps = emoji.codePoints().toArray();
StringBuilder cpb = new StringBuilder();
for (int i = cps.length - 1; i >= 0; i--) cpb.appendCodePoint(cps[i]);

P30 'a'+grinning-face+'b': length() / codePointCount -> 4 / 3
P30 char-by-char reverse UTF-16 units -> 0062 DE00 D83D 0061 (equals correct reverse: false)
P30 StringBuilder.reverse UTF-16 units -> 0062 D83D DE00 0061 (equals correct reverse: true)
P30 codePoints-based reverse equals correct -> true

Source: StringInterviewPrograms.java, main section P30, reverseBrute, reverseOpt