When the problem is really a string problem
Strings are arrays with an alphabet and awkward mutability rules. Interviewers love them because they mix two-pointer, hashing, and expand-around-center in one costume. Open with: immutable string → build with a buffer; indices are still array indices.
Analogy: beads on a string
A string is a necklace of beads. Two pointers walk from the ends checking symmetry (palindrome). Expanding around a center is pinching one bead (or a gap between beads) and walking outward while the beads match. A StringBuilder is a new necklace you assemble on the table — never splice the original mid-flight in Java.
Two pointers on characters
Skip non-alphanumeric for Valid Palindrome. For reverse words, reverse the whole buffer then reverse each word span. Always clarify: case fold? Unicode? Whitespace collapse?
def is_palindrome(s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True
# Trace: "A man, a plan, a canal: Panama" → Trueboolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
i++; j--;
}
return true;
}Expand around center
Longest palindromic substring in O(n²): for each center (2n−1 centers: chars and gaps), expand while equal. Manacher is O(n) but rarely expected — say you know it exists, then ship expand-around-center.
def longest_palindrome(s: str) -> str:
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return l + 1, r - 1 # inclusive
best_l, best_r = 0, 0
for i in range(len(s)):
for l, r in (expand(i, i), expand(i, i + 1)):
if r - l > best_r - best_l:
best_l, best_r = l, r
return s[best_l : best_r + 1]
# O(n^2) time, O(1) extraString longestPalindrome(String s) {
int bl = 0, br = 0;
for (int i = 0; i < s.length(); i++) {
int[] a = expand(s, i, i);
int[] b = expand(s, i, i + 1);
int[] best = a[1] - a[0] >= b[1] - b[0] ? a : b;
if (best[1] - best[0] > br - bl) { bl = best[0]; br = best[1]; }
}
return s.substring(bl, br + 1);
}
int[] expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return new int[]{l + 1, r - 1};
}Building strings safely
def reverse_words(s: str) -> str:
words = s.split() # collapses whitespace
return " ".join(reversed(words))
# " hello world " → "world hello"String reverseWords(String s) {
String[] parts = s.trim().split("\\s+");
StringBuilder sb = new StringBuilder();
for (int i = parts.length - 1; i >= 0; i--) {
sb.append(parts[i]);
if (i > 0) sb.append(' ');
}
return sb.toString();
}Edges interviewers love
What to say in the first 60 seconds
String rounds go sideways when you mutate an immutable Java string in a loop or forget even-length palindrome centers. Narrate the center types before you touch the keyboard.
Tradeoffs vs windows and tries
If the interviewer says “longest substring without repeating characters,” you are in the window post — say so and switch. Pattern recognition is the skill; don’t drag expand-center into a window problem.
Pattern bank (5 questions)
Q: Valid Palindrome — ignore non-alphanumeric; case-insensitive.
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum(): i += 1
while i < j and not s[j].isalnum(): j -= 1
if s[i].lower() != s[j].lower(): return False
i += 1; j -= 1
return Trueboolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
i++; j--;
}
return true;
}Q: Longest Palindromic Substring — return any longest palindromic substring.
def longest_palindrome(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return l + 1, r - 1
bl = br = 0
for i in range(len(s)):
for L, R in (expand(i, i), expand(i, i + 1)):
if R - L > br - bl: bl, br = L, R
return s[bl:br + 1]String longestPalindrome(String s) {
int bl = 0, br = 0;
for (int i = 0; i < s.length(); i++) {
for (int[] pair : new int[][]{expand(s,i,i), expand(s,i,i+1)}) {
if (pair[1] - pair[0] > br - bl) { bl = pair[0]; br = pair[1]; }
}
}
return s.substring(bl, br + 1);
}
int[] expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return new int[]{l + 1, r - 1};
}Q: Reverse Words in a String — reverse word order; collapse spaces.
def reverse_words(s):
return " ".join(reversed(s.split()))String reverseWords(String s) {
String[] p = s.trim().split("\\s+");
StringBuilder sb = new StringBuilder();
for (int i = p.length - 1; i >= 0; i--) {
sb.append(p[i]);
if (i > 0) sb.append(' ');
}
return sb.toString();
}Q: Longest Common Prefix — longest shared prefix of an array of strings.
def longest_common_prefix(strs):
if not strs: return ""
for i, ch in enumerate(strs[0]):
for s in strs[1:]:
if i >= len(s) or s[i] != ch:
return strs[0][:i]
return strs[0]String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
for (int i = 0; i < strs[0].length(); i++) {
char ch = strs[0].charAt(i);
for (int j = 1; j < strs.length; j++) {
if (i >= strs[j].length() || strs[j].charAt(i) != ch)
return strs[0].substring(0, i);
}
}
return strs[0];
}Q: Encode and Decode Strings — design encode/decode for a list of strings (may contain any char).
def encode(strs):
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(s):
out, i = [], 0
while i < len(s):
j = s.index("#", i)
n = int(s[i:j])
out.append(s[j + 1 : j + 1 + n])
i = j + 1 + n
return outString encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String s : strs) sb.append(s.length()).append('#').append(s);
return sb.toString();
}
List<String> decode(String s) {
List<String> out = new ArrayList<>();
int i = 0;
while (i < s.length()) {
int j = s.indexOf('#', i);
int n = Integer.parseInt(s.substring(i, j));
out.add(s.substring(j + 1, j + 1 + n));
i = j + 1 + n;
}
return out;
}