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 = [Link]() - 1; i >= 0; i--) {
res += [Link](i); // O(i) each due to immutability
}
return res;
}
}
JavaScript
function reverseBrute(s) {
let res = "";
for (let i = [Link] - 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 = [Link]();
int i = 0, j = [Link] - 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 = [Link](s); // handles surrogate pairs better than split("")
let i = 0, j = [Link] - 1;
while (i < j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; }
return [Link]("");
}
Explanation
Copy to a mutable array (`char[]` in Java or character array in JS), swap ends inward. Exactly ■n/2■ swaps.
For JS, `[Link](s)` is preferred over `[Link]('')` 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 [Link].*;
public class ReverseString_Stack {
public static String reverse(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : [Link]()) [Link](c);
StringBuilder sb = new StringBuilder([Link]());
while (![Link]()) [Link]([Link]());
return [Link]();
}
}
JavaScript
function reverseStack(s) {
const st = [];
for (const c of s) [Link](c);
let out = "";
while ([Link]) out += [Link]();
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([Link](), 0, [Link]() - 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 = [Link](s);
function rec(i, j) {
if (i >= j) return [Link]("");
[a[i], a[j]] = [a[j], a[i]];
return rec(i + 1, j - 1);
}
return rec(0, [Link] - 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 [Link];
import [Link].*;
public class ReverseString_Grapheme {
public static String reverseByGrapheme(String s, Locale locale) {
BreakIterator it = [Link](locale);
[Link](s);
List<String> clusters = new ArrayList<>();
int start = [Link]();
for (int end = [Link](); end != [Link]; start = end, end = [Link]()) {
[Link]([Link](start, end));
}
[Link](clusters);
return [Link]("", clusters);
}
}
JavaScript ([Link])
// Grapheme-safe reverse with [Link] (Node 14+/modern browsers)
function reverseByGrapheme(s, locale = 'en') {
if (typeof Intl !== 'undefined' && [Link]) {
const seg = new [Link](locale, { granularity: 'grapheme' });
const clusters = [Link]([Link](s), seg => [Link]);
[Link]();
return [Link]('');
}
// Fallback (may break grapheme clusters):
return [Link](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.