Remove Occurrences of a Character
Ramayana — Hanuman's Purge — Remove All Demons from the Sacred Path
अपवित्र अक्षर हटाओ — शेष रखो। पहला देखो — मिले तो छोड़ो, नहीं तो जोड़ो॥
*Remove the impure character — keep the rest. Check the first — if it matches, skip; otherwise keep.*
The Story
Remove all occurrences of character c from string s using recursion.
For `s="aabbcc"`, `c='b'`: return "aacc".
**Recursive approach:** - Base: s is empty → return "" - Recursive: if s[0]==c, skip it: return remove(s.substring(1), c) - Otherwise: keep it: return s[0] + remove(s.substring(1), c)
```java String remove(String s, char c) { if (s.isEmpty()) return ""; // Base case if (s.charAt(0) == c) return remove(s.substring(1), c); // Skip matching char return s.charAt(0) + remove(s.substring(1), c); // Keep non-matching } ```
Trace `s="abc"`, `c='b'`: - remove("abc",'b'): 'a'≠'b' → 'a' + remove("bc",'b') - remove("bc",'b'): 'b'=='b' → remove("c",'b') - remove("c",'b'): 'c'≠'b' → 'c' + remove("",'b') - remove("",'b'): return "" - Returns: 'c'+""="c" → remove "c" → 'a'+"c"="ac" ✓
This is the **filter** pattern: keep only elements that satisfy a condition, expressed recursively.
**Iterative alternative:** ```java StringBuilder sb = new StringBuilder(); for (char ch : s.toCharArray()) if (ch != c) sb.append(ch); return sb.toString(); ```
The StringBuilder Filter
Iterate, append non-matching chars to StringBuilder. O(n), O(n) space.
String removeIterative(String s, char c) {
StringBuilder sb = new StringBuilder();
for (char ch : s.toCharArray())
if (ch != c) sb.append(ch);
return sb.toString();
}The First-Char-Filter Recursion
String remove(String s, char c) {
if (s.isEmpty()) return "";
return (s.charAt(0) == c ? "" : String.valueOf(s.charAt(0)))
+ remove(s.substring(1), c);
}Step-by-Step Walkthrough
remove("", 'a') = "" ✅
remove("aaa",'a') = remove("aa",'a') = remove("a",'a') = remove("",'a') = "" ✅Deep Insight
**The filter recursion pattern:** Process the first element and recurse on the rest. This pattern underlies many functional programming operations (map, filter, reduce) expressed recursively.
**`substring(1)` creates a new string each time** — O(n) per call, O(n²) total if building up. In Java, this is not ideal. The iterative StringBuilder approach is O(n).
**Recursive string operations:** String immutability in Java means recursion naturally creates new strings at each step. When combining recursion with string building, watch out for quadratic complexity.
**Pattern for rb-5:** This is `filter` — keep elements matching a condition. Compare with `map` (transform each element) and `fold` (accumulate, like rb-4's digit sum).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | StringBuilder iteration |
| Optimal | O(n²) | O(n) | O(n) calls × O(n) substring each = O(n²); prefer iterative |
Pattern Recognition
✅ Filter pattern: skip matching, keep non-matching ✅ Base: empty string → return "" ✅ Process first element, recurse on rest ✅ Prefer iterative for actual performance **LeetCode Trigger Phrases:** → "remove all occurrences" of character → Filter characters from string → Recursive first-element processing
Bhagavad Gita 3.19
तस्माद् असक्तः सततं कार्यं कर्म समाचर। असक्तो ह्याचरन्कर्म परमाप्नोति पूरुषः॥
Therefore, always perform actions that should be done, without attachment. By performing action without attachment, one attains the Supreme.
Connection: The algorithm removes what doesn't belong (the target character) and keeps what does — a purification process performed systematically, character by character, without attachment to any particular outcome. Like the Gita's teaching on desireless action, the algorithm processes each element objectively, neither clinging to those it keeps nor dwelling on those it removes, arriving at the purified string through steady, unattached work.