Problem 1 — Reverse A String (Java & JavaScript)
Multi■Approach Guide: Brute Force · Two■Pointer · Stack · Recursion · Unicode■Safe Variant · Why DP/Greedy
don’t add value here. Includes diagrams and complexity analysis.
Problem Statement
Given a string s, return its reverse.
Example
Input: "interview" → Output: "weivretni"
Input: "ab■c" → Output: "c■ba" (note: emoji is a multi-byte character)
Key Diagrams
Approach A — Brute Force (Reverse Concatenation)
Java
public class ReverseString_BruteConcat {
// Brute force: concatenate characters in reverse order
public static String reverse(String s) {
String res = "";
for (int i = s.length() - 1; i >= 0; i--) {
res += s.charAt(i); // O(i) each due to immutability
}
return res;
}
}
JavaScript
function reverseBrute(s) {
let res = "";
for (let i = s.length - 1; i >= 0; i--) {
res += s[i]; // O(i) each due to immutability
}
return res;
}
Explanation
Append characters from right to left. Because strings are immutable, repeated concatenation copies partial
results repeatedly, causing quadratic time.
Time & Space Complexity
Time: O(n²). Space: O(n) for the resulting string.
Approach B — Two■Pointer (Optimal for arrays/char[])
Java
public class ReverseString_TwoPointer {
public static String reverse(String s) {
char[] a = s.toCharArray();
int i = 0, j = a.length - 1;
while (i < j) {
char t = a[i]; a[i] = a[j]; a[j] = t;
i++; j--;
}
return new String(a);
}
}
JavaScript
function reverseTwoPointer(s) {
const a = Array.from(s); // handles surrogate pairs better than split("")
let i = 0, j = a.length - 1;
while (i < j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; }
return a.join("");
}
Explanation
Copy to a mutable array (`char[]` in Java or character array in JS), swap ends inward. Exactly ■n/2■ swaps.
For JS, `Array.from(s)` is preferred over `s.split('')` for better handling of surrogate pairs.
Time & Space Complexity
Time: O(n). Space: O(n) for the array/new string; O(1) extra if an in■place mutable buffer is allowed.
Approach C — Using A Stack
Java
import java.util.*;
public class ReverseString_Stack {
public static String reverse(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) st.push(c);
StringBuilder sb = new StringBuilder(s.length());
while (!st.isEmpty()) sb.append(st.pop());
return sb.toString();
}
}
JavaScript
function reverseStack(s) {
const st = [];
for (const c of s) st.push(c);
let out = "";
while (st.length) out += st.pop();
return out;
}
Explanation
Push all characters, then pop to reverse order. Educational, but more overhead than two■pointer.
Time & Space Complexity
Time: O(n). Space: O(n) for the stack.
Approach D — Recursion (Divide & Swap)
Java
public class ReverseString_Recursion {
public static String reverse(String s) {
return rec(s.toCharArray(), 0, s.length() - 1);
}
private static String rec(char[] a, int i, int j) {
if (i >= j) return new String(a);
char t = a[i]; a[i] = a[j]; a[j] = t;
return rec(a, i + 1, j - 1);
}
}
JavaScript
function reverseRec(s) {
const a = Array.from(s);
function rec(i, j) {
if (i >= j) return a.join("");
[a[i], a[j]] = [a[j], a[i]];
return rec(i + 1, j - 1);
}
return rec(0, a.length - 1);
}
Explanation
Swap outer pair and recurse inward. Elegant but uses call stack; watch for recursion limits with very long
strings.
Time & Space Complexity
Time: O(n). Space: O(n) due to recursion depth.
Unicode■Safe Variant (Grapheme Clusters)
Java (ICU/BreakIterator sketch)
// Grapheme-safe reverse (requires ICU4J if you need full grapheme cluster support).
// Here is a sketch using BreakIterator for user-perceived characters (not perfect for all cases):
import java.text.BreakIterator;
import java.util.*;
public class ReverseString_Grapheme {
public static String reverseByGrapheme(String s, Locale locale) {
BreakIterator it = BreakIterator.getCharacterInstance(locale);
it.setText(s);
List<String> clusters = new ArrayList<>();
int start = it.first();
for (int end = it.next(); end != BreakIterator.DONE; start = end, end = it.next()) {
clusters.add(s.substring(start, end));
}
Collections.reverse(clusters);
return String.join("", clusters);
}
}
JavaScript (Intl.Segmenter)
// Grapheme-safe reverse with Intl.Segmenter (Node 14+/modern browsers)
function reverseByGrapheme(s, locale = 'en') {
if (typeof Intl !== 'undefined' && Intl.Segmenter) {
const seg = new Intl.Segmenter(locale, { granularity: 'grapheme' });
const clusters = Array.from(seg.segment(s), seg => seg.segment);
clusters.reverse();
return clusters.join('');
}
// Fallback (may break grapheme clusters):
return Array.from(s).reverse().join('');
}
Explanation
Some user■perceived characters (graphemes) are composed of multiple code points. Reversing by code
units can split them incorrectly. Segment into grapheme clusters and reverse those for correct visual results.
Time & Space Complexity
Time: O(n) over clusters (plus segmentation cost). Space: O(n) for the cluster list.
Why DP & Greedy Don’t Add Value Here
There’s no optimization frontier or overlapping■subproblem structure that improves upon the O(n)
two■pointer method. Two■pointer already achieves optimal work with constant extra memory (on a mutable
buffer). Greedy/DP are unnecessary.
Edge Cases & Testing Notes
• Empty string → empty result. • Single character → same string. • All identical characters. • Unicode with
surrogate pairs and combining marks. • Very long strings (prefer iterative methods over recursion).
Summary
Use the two■pointer method for performance and simplicity. Employ a grapheme■aware reversal when exact
Unicode rendering is required.
