String Manipulation Problem Set
A themed set of the string problems that show up first in almost every technical interview — reversing, palindrome checks, anagram checks, and sliding-window substring problems — taught through the reasoning that gets you to an optimal solution, not just the final code.
Learning objectives
- Reverse a string in place using the two-pointer technique and explain why character arrays make in-place mutation possible in Java
- Distinguish a strict palindrome check from the 'valid palindrome ignoring non-alphanumeric characters' variant and adapt the two-pointer pattern to skip characters
- Determine whether two strings are anagrams using both a frequency-count array and a sorting-based approach, and explain the time/space tradeoff between them
- Find the first non-repeating character in a string using a single frequency pass followed by an ordered second pass
- Apply the sliding-window technique to find the longest substring without repeating characters, tracking a window with a hash set or index map
- Recognize when a brute-force O(n^2) or O(n^3) string approach can be collapsed into a single linear pass using two pointers or a sliding window
Problem Story
Imagine you're building a simple text utility for a chat application, and one of the features product has asked for is a 'mirror mode' that reverses whatever the user typed, purely for fun, before sending it. It sounds trivial until you remember that a String in Java is immutable — every time you think you're 'reversing' it with naive concatenation, you're secretly allocating a brand new String object for every character you append. For a short chat message that's invisible. For a batch job reversing millions of log lines, it's the difference between a job that finishes in seconds and one that chews through memory doing needless allocation. This is the problem that teaches you to stop thinking of a string as text and start thinking of it as an array of characters you can manipulate directly, the same mental shift that underlies almost every other string problem in this set.
Approach & Solution
The laziest correct solution builds a new string by walking the original from the last character to the first and appending each character to a StringBuilder. That's O(n) time, but it still treats the string as something you read, not something you mutate — useful for intuition, but it misses the technique interviewers are actually probing for.
The technique that matters is the two-pointer in-place swap. Convert the string into a char array (Java gives you toCharArray() for exactly this reason — it's the escape hatch out of immutability). Set one pointer, left, at index 0 and another, right, at the last index. Swap the characters at left and right, then move left forward and right backward. Keep going until left and right meet or cross in the middle. Each swap places two characters in their final position in a single operation, so the whole array is correctly reversed after exactly n/2 swaps — half the work of visiting every index individually, and done with O(1) extra space beyond the array itself, since you never allocate a second array or a growing buffer.
Walk through "hello": left=0 ('h'), right=4 ('o'). Swap them: "oellh". Move to left=1 ('e'), right=3 ('l'). Swap: "olleh" — wait, let's be precise: after the first swap the array is o-e-l-l-h, then swapping index 1 and 3 ('e' and 'l') gives o-l-l-e-h, and left becomes 2 which now equals right-1's neighbor... the key invariant is simply that the loop runs while left < right, and on each iteration exactly one pair is finalized. For a 5-character string that's 2 swaps and the middle character ('l' at index 2) never moves because it's already in its correct final position.
The reason this pattern recurs across so many interview problems — palindrome checking, array rotation, removing duplicates — is that it converts any problem framed as 'process from both ends toward the middle' into a single linear pass with constant extra space. Once you've internalized reversing a char array with two pointers, the palindrome check in the next lesson is almost the same loop with one extra condition.
One trap worth naming explicitly: if you're asked to reverse a String object (not a char array) in place, the honest answer is that you can't — String is immutable in Java by design, backed by a final char array internally, specifically so that strings can be safely shared, cached, and used as HashMap keys without defensive copying. The best you can do is reverse a mutable copy (a char array or a StringBuilder) and return a new String from it. Saying this out loud in an interview is itself a signal that you understand the language, not just the algorithm.
💻 Code example
public class StringReversal { // Reverses a char array in place using the two-pointer technique. // Time: O(n), Space: O(1) extra (beyond the array itself). public static void reverseInPlace(char[] chars) { int left = 0; int right = chars.length - 1; while (left < right) { char temp = chars[left]; chars[left] = chars[right]; chars[right] = temp; left++; right--; } } // Convenience wrapper: String is immutable, so this returns a NEW // String built from a reversed copy of the original's characters. public static String reverse(String input) { if (input == null) return null; char[] chars = input.toCharArray(); reverseInPlace(chars); return new String(chars); } public static void main(String[] args) { System.out.println(reverse("hello")); // olleh System.out.println(reverse("interview")); // weivretni System.out.println(reverse("")); // (empty string) } }
Problem Story
A form validation library you're maintaining needs to flag palindromic usernames as a fun badge-unlock feature — "anna", "racecar", that sort of thing. Easy enough. Then a ticket comes in: a user typed "A man, a plan, a canal: Panama" into a free-text field and complained the badge didn't unlock, even though to any human reading it, that sentence is obviously a palindrome once you ignore spaces, punctuation, and letter case. This is where a seemingly solved problem reopens — you now need two versions of the same idea: a strict check for clean, pre-sanitized input, and a tolerant check that filters noise before comparing.
Approach & Solution
The strict version is the direct application of the two-pointer pattern from the previous lesson. Put left at index 0 and right at the last index. If chars[left] != chars[right], you can return false immediately — no palindrome survives a single mismatched pair. If they match, move both pointers inward. If the pointers meet or cross without ever finding a mismatch, the string is a palindrome. This runs in O(n) time with O(1) extra space, and never needs to build a reversed copy of the string at all, which is strictly better than the tempting but wasteful 'reverse the string and check if it equals the original' approach — that version does roughly twice the work and allocates a second string for no benefit.
The valid-palindrome variant adds exactly one responsibility to the same loop: skip characters that aren't letters or digits before comparing, and compare case-insensitively. The clean way to do this is to advance left while it's pointing at a non-alphanumeric character, and advance right the same way, before doing the comparison — not as a separate preprocessing pass that builds a filtered copy of the string, which would cost extra space, but as an inline skip inside the same while loop. Concretely: inside the main loop, run an inner while that increments left past non-alphanumeric characters (guarding against left exceeding right), run another inner while that decrements right past non-alphanumeric characters, and only then compare Character.toLowerCase(chars[left]) to Character.toLowerCase(chars[right]). If after skipping, left >= right, you're done and it's a palindrome. This keeps the whole check at O(n) time and O(1) extra space — you never materialize a cleaned string, you just navigate around the noise in place.
Trace "A man, a plan, a canal: Panama": left starts at 'A', right at the final 'a'. Both are letters, lowercase both to 'a' — match, pointers move inward. Eventually left lands on the space after 'A', which gets skipped by the inner while; right lands on 'a' in 'Panama' which is kept. The algorithm keeps weaving past commas, colons, and spaces on both sides, always doing the real letter-to-letter comparisons, and reports true.
The lesson that generalizes beyond this specific problem is this: whenever you're asked to 'validate ignoring noise,' resist the urge to build a cleaned copy of the input first. It's always correct, but it's rarely optimal, and interviewers specifically listen for whether you can fold the filtering into the same pass as the actual check. That skill — doing two logical jobs in one physical loop — comes up again in the longest-substring and anagram problems later in this set.
💻 Code example
public class PalindromeChecks { // Strict palindrome check: every character must match exactly. public static boolean isStrictPalindrome(String s) { int left = 0; int right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) return false; left++; right--; } return true; } // "Valid Palindrome": ignore non-alphanumeric characters and case. // Time: O(n), Space: O(1) extra. public static boolean isValidPalindrome(String s) { int left = 0; int right = s.length() - 1; while (left < right) { while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { left++; } while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { right--; } char leftChar = Character.toLowerCase(s.charAt(left)); char rightChar = Character.toLowerCase(s.charAt(right)); if (leftChar != rightChar) return false; left++; right--; } return true; } public static void main(String[] args) { System.out.println(isStrictPalindrome("racecar")); // true System.out.println(isStrictPalindrome("hello")); // false System.out.println(isValidPalindrome("A man, a plan, a canal: Panama")); // true System.out.println(isValidPalindrome("race a car")); // false } }
Problem Story
A puzzle game you're building lets players submit a word, and the game needs to confirm it's a valid rearrangement of a target word's letters — "listen" should match "silent", but "listens" shouldn't, and neither should "listen " with a trailing space that the player's keyboard app sneakily inserted. The naive instinct is to compare sorted versions of both strings, and that instinct is actually a perfectly good solution — the question is whether you can also produce the faster one, and explain when each is the better choice.
Approach & Solution
Before any comparison, check lengths. Two strings of different lengths can never be anagrams of each other, and catching this first avoids wasted work on inputs that are obviously disqualified — a cheap O(1) check that short-circuits the expensive part of the algorithm.
The sorting approach converts both strings to char arrays, sorts each with Arrays.sort (which is O(n log n)), and compares the sorted arrays with Arrays.equals. If the sorted character sequences are identical, the original strings are anagrams, because sorting is a canonical form — any two strings with the same multiset of characters sort to the exact same array. This is simple to write and simple to reason about, and it's genuinely the right choice when n is small or when you want code that is obviously correct at a glance, such as in a one-off script. Its cost is the O(n log n) sort.
The frequency-count approach does better: O(n) time, O(1) extra space if you assume a fixed alphabet like lowercase English letters (26 possible characters, so a size-26 int array is constant space regardless of input length). Walk the first string and, for each character, increment counts[c - 'a']. Walk the second string and, for each character, decrement counts[c - 'a']. If the strings are true anagrams, every increment from the first walk is exactly canceled by a decrement from the second walk, and the counts array ends up all zeros. If any count is nonzero at the end, some character appeared a different number of times in the two strings, and they are not anagrams. You can even short-circuit during the second pass: if decrementing ever drives a count below zero, that means the second string used a character more times than the first string offered, which is an instant disqualification — no need to finish the pass.
This single-array trick is worth dwelling on because it replaces two separate frequency maps (one per string, which you'd then have to compare entry by entry) with one array that self-cancels. It's a pattern that reappears constantly in problems with 'the net effect of two multisets must be identical' at their core — the sliding-window variant of this problem (find anagram substrings inside a larger text) uses the exact same canceling-counts idea, just inside a moving window instead of over the whole string once.
For inputs beyond a known fixed alphabet — Unicode text, for instance — a HashMap<Character, Integer> replaces the fixed-size array, trading the O(1)-space guarantee for generality: still O(n) time, but O(k) space where k is the number of distinct characters encountered. Knowing which version to reach for, and being able to name the tradeoff out loud, matters more to an interviewer than memorizing either implementation.
💻 Code example
import java.util.Arrays; public class AnagramCheck { // O(n log n) time, O(n) space — simple and obviously correct. public static boolean isAnagramBySorting(String a, String b) { if (a.length() != b.length()) return false; char[] arrA = a.toCharArray(); char[] arrB = b.toCharArray(); Arrays.sort(arrA); Arrays.sort(arrB); return Arrays.equals(arrA, arrB); } // O(n) time, O(1) extra space for lowercase a-z input. public static boolean isAnagramByCount(String a, String b) { if (a.length() != b.length()) return false; int[] counts = new int[26]; for (char c : a.toCharArray()) { counts[c - 'a']++; } for (char c : b.toCharArray()) { counts[c - 'a']--; if (counts[c - 'a'] < 0) return false; // b used a char too many times } for (int count : counts) { if (count != 0) return false; } return true; } public static void main(String[] args) { System.out.println(isAnagramByCount("listen", "silent")); // true System.out.println(isAnagramByCount("listen", "listens")); // false System.out.println(isAnagramBySorting("rat", "tar")); // true } }
Problem Story
A username generator needs a 'uniqueness hint' feature: given a candidate username, highlight the first character that doesn't repeat anywhere else in the string, as a playful way to show the user what makes their handle distinctive. For "swiss", that's 'w' — 's' repeats three times, 'i' doesn't repeat but 'w' comes first. This is a small problem, but it's the cleanest teaching example of a two-pass pattern that shows up whenever you need to answer a question about order and frequency at the same time.
Approach & Solution
A single pass can tell you how many times each character appears, but it cannot by itself tell you which character came first among the ones that appear exactly once — frequency and position are two different pieces of information, and one pass only accumulates the first kind. The clean solution is therefore two passes, each doing one job.
Pass one builds a frequency count, exactly like in the anagram problem: walk the string once and, for each character, increment its count in either a size-128 (or size-256) array indexed by the character's numeric value, or a HashMap<Character, Integer> if you want to support the full Unicode range. This pass is O(n) and tells you, for any character, how many times it occurs anywhere in the string — but it doesn't yet tell you which one to report, because the answer depends on original order, which a frequency table doesn't preserve.
Pass two walks the string again, this time in original left-to-right order, and for each character checks its count from pass one. The moment you find a character whose count is exactly 1, you return it immediately — because you're walking in original order, the first one you encounter with count 1 is, by definition, the first non-repeating character in the whole string. If you reach the end of the second pass without finding any character with count 1, every character repeats, and you return a sentinel value (commonly '\0' or a documented -1/null, depending on the return type) to signal 'no such character exists.'
The total cost is two linear passes, so still O(n) time overall, and O(1) extra space if you commit to a fixed small alphabet (ASCII), or O(k) for a HashMap over a larger alphabet where k is the number of distinct characters. The reason this is worth dwelling on past the code itself is the general lesson: when a problem needs you to reason about both 'how many times' and 'in what order,' a single pass is usually not enough, no matter how clever the loop body gets — you need one pass to gather the aggregate fact and a second pass, in the original order that matters, to apply it. Trying to force this into one pass usually produces code that's harder to read and no faster, since the second pass is already O(n) and can't be skipped without losing the ordering information.
One implementation detail worth getting right: don't use a LinkedHashMap thinking it 'solves' the ordering problem by magic — it only helps if you're careful about exactly when entries are inserted and in what order you iterate them, and for this specific problem the explicit two-array/two-pass version is more obviously correct and easier to explain out loud, which matters more in an interview than a one-liner using a fancier collection.
💻 Code example
public class FirstNonRepeatingChar { // Two-pass solution. Time: O(n), Space: O(1) for ASCII input. // Returns the first non-repeating character, or '\0' if none exists. public static char firstNonRepeating(String s) { int[] counts = new int[256]; // Pass 1: build frequency counts. for (char c : s.toCharArray()) { counts[c]++; } // Pass 2: walk in original order, return the first count-1 char. for (char c : s.toCharArray()) { if (counts[c] == 1) { return c; } } return '\0'; // sentinel: no non-repeating character found } public static void main(String[] args) { System.out.println(firstNonRepeating("swiss")); // w System.out.println(firstNonRepeating("aabbcc")); // \0 (none) System.out.println(firstNonRepeating("teeter")); // r } }
Problem Story
A password strength checker wants to flag passwords that lean too heavily on repeated characters by measuring the longest stretch of genuinely distinct characters anywhere inside the password. For "abcabcbb" that stretch is "abc", length 3; for "pwwkew" it's "wke", length 3, even though a careless eye might first spot "pw" and "kew" separately without noticing "wke" bridges across the repeated 'w'. This problem is the natural next step after the anagram and first-non-repeating problems, because it asks you to track uniqueness not over the whole string, but over a moving window inside it — which is exactly what the sliding window technique was built for.
Approach & Solution
The brute-force approach checks every possible substring for uniqueness, which is O(n^2) substrings each taking up to O(n) to verify, for O(n^3) overall — correct, but far too slow to be the final answer in an interview setting, and a useful baseline mainly for sanity-checking the faster solution against small examples.
The sliding window approach maintains a window defined by two pointers, left and right, that always represents a substring with no repeated characters, and a HashMap<Character, Integer> that records the most recent index at which each character was seen. Walk right from 0 to the end of the string, one character at a time. For each character at position right, check whether it's already in the map with an index that falls inside the current window (that is, its last-seen index is >= left). If so, a repeat has entered the window, so jump left forward to one past that character's last-seen index — this discards exactly the prefix of the window that contained the earlier occurrence, in one O(1) jump, rather than shrinking the window one character at a time. Then, regardless of whether a jump happened, record the current character's index in the map (overwriting any stale entry), and update the best-length-so-far as right - left + 1, the size of the current valid window. Because each character is visited once by right and left only ever moves forward, never backward, the whole algorithm is O(n) time, with O(min(n, alphabet size)) space for the map.
Trace "pwwkew": right=0 sees 'p', map empty, window is "p", length 1. right=1 sees 'w', not in window, window is "pw", length 2. right=2 sees 'w' again — it IS in the window (last seen at index 1, which is >= left=0), so left jumps to 2 (one past index 1). Window is now just "w" at index 2, length 1. right=3 sees 'k', window "wk", length 2. right=4 sees 'e', window "wke", length 3 — this is the new best. right=5 sees 'w' again, but its last-seen index (2) is now less than left (2)... actually equal to left, which still counts as inside the window, so left jumps to 3. Window becomes "ke" plus the new 'w' — "kew", length 3, tying the best. Final answer: 3.
The one off-by-one trap everyone hits on this problem is the jump condition: you must only jump left when the character's last-seen index is inside the current window (>= left), not simply because the character was seen before at any point in the string's history. A character seen long ago, before the window's current left boundary, is irrelevant — it already fell out of the window and its old index must not cause a spurious jump. Getting this condition wrong either shrinks the window too aggressively (wrong, too-small answers) or not aggressively enough (wrong, answers that silently include a repeat). This exact 'is the stale data still relevant to my current window' check is the crux of nearly every sliding-window problem you'll encounter, including window-based anagram search and minimum-window-substring variants of this same family.
💻 Code example
import java.util.HashMap; import java.util.Map; public class LongestSubstringWithoutRepeats { // Sliding window. Time: O(n), Space: O(min(n, alphabet size)). public static int lengthOfLongestSubstring(String s) { Map<Character, Integer> lastSeenIndex = new HashMap<>(); int left = 0; int best = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); if (lastSeenIndex.containsKey(c) && lastSeenIndex.get(c) >= left) { // c repeats inside the current window: shrink from the left // past its earlier occurrence in one jump. left = lastSeenIndex.get(c) + 1; } lastSeenIndex.put(c, right); best = Math.max(best, right - left + 1); } return best; } public static void main(String[] args) { System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc") System.out.println(lengthOfLongestSubstring("pwwkew")); // 3 ("wke") System.out.println(lengthOfLongestSubstring("bbbbb")); // 1 ("b") } }
Want a visual for this concept?
Generate a diagram tailored to “String Manipulation Problem Set” — the AI picks whichever visual (flowchart, comparison, sequence, etc.) best fits.
Sign in to generate a visual →