DSA Day 67: String Manipulation & State Tracking

📅 Date: June 18, 2026

🧠 Mood: The Filter 🚰

🔥 Topic: DSA Day 67: String Manipulation & State Tracking

📝 Passing the Memory Baton

If I asked you to remove all duplicate letters from a string like "appnnacollege", your first instinct would probably be to use a for loop and a Hash Set. It's fast, it's easy, and it works. But the current module isn't about finding the easiest way out; it's about forcing the brain to understand deep recursion.

The challenge today was to remove duplicates recursively. The difficulty here is that recursive functions are isolated. When function(index 2) runs, it has absolutely no idea what function(index 1) did, unless you explicitly pass that information down the chain. I had to learn how to track "State" across multiple levels of the Call Stack.

---

🗺️ The Boolean Map Strategy

To solve this, we create a boolean array of size 26 (representing every lowercase letter from 'a' to 'z'). As the recursive function traverses the string character by character, it checks this map.

• If the current character's slot in the map is false, it means we are seeing this letter for the first time. We append it to our new string, mark the map as true, and recurse forward.
• If the map is already true, it's a duplicate. We ignore it, append nothing, and recurse forward.

---

💻 The C++ Implementation

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void removeDuplicates(string str, int idx, string newStr, vector<bool>& map) {
    // 1. BASE CASE: Reached the end of the string
    if (idx == str.length()) {
        cout << "Clean String: " << newStr << endl;
        return;
    }

    // Get the current character
    char currChar = str[idx];
    
    // Map character 'a'-'z' to index 0-25
    int mapIndex = currChar - 'a'; 

    // 2. RECURSIVE CHOICES
    if (map[mapIndex] == true) {
        // Duplicate found: Skip it and move to next index
        removeDuplicates(str, idx + 1, newStr, map);
    } else {
        // First time seeing it: Mark as true, add to string, move forward
        map[mapIndex] = true;
        removeDuplicates(str, idx + 1, newStr + currChar, map);
    }
}

int main() {
    string dirtyString = "appnnacollege";
    vector<bool> characterMap(26, false);
    
    removeDuplicates(dirtyString, 0, "", characterMap);
    // Output: Clean String: apncoleg
    return 0;
}

---

🎯 The Power of State

Passing the vector<bool> by reference ensures that every single recursive call is looking at the exact same tracker in memory. Tomorrow, we finish this module with hardcore Combinatorics: The Friends Pairing Problem and Binary Strings.