Remove Duplicate Letters - CPP Solution

1. Introduction

This blog post delves into an intriguing string manipulation problem in C++: removing duplicate letters from a string such that the resulting string is the smallest in lexicographical order. This problem is a good exercise in understanding string processing, greedy algorithms, and stack usage in C++.

Problem

Given a string s, the goal is to remove duplicate letters so that every letter appears once and only once. The key is to ensure that the resulting string is the smallest in lexicographical order among all possible results.

2. Solution Steps

1. Count the occurrences of each character in the string.

2. Use a stack to keep track of the characters in the result string.

3. Use a boolean array to mark which characters are in the stack.

4. Iterate through each character in the string:

- Decrement the character's count in the occurrence map.

- If the character is not already in the stack, push it onto the stack.

- Ensure that the stack is lexicographically smallest by popping characters that are greater than the current character and can appear later.

5. Build the resulting string from the stack.

3. Code Program

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

// Function to remove duplicate letters and return the smallest lexicographical order string
string removeDuplicateLetters(string s) {
    vector<int> charCount(256, 0);
    vector<bool> inStack(256, false);
    stack<char> st;

    // Count occurrences of each character
    for (char c : s) {
        charCount[c]++;
    }

    for (char c : s) {
        charCount[c]--;
        if (inStack[c]) continue;

        // Ensure the stack is lexicographically smallest
        while (!st.empty() && st.top() > c && charCount[st.top()] > 0) {
            inStack[st.top()] = false;
            st.pop();
        }

        st.push(c);
        inStack[c] = true;
    }

    // Build the result string from the stack
    string result = "";
    while (!st.empty()) {
        result = st.top() + result;
        st.pop();
    }
    return result;
}

int main() {
    string s = "cbacdcbc";
    cout << "Result: " << removeDuplicateLetters(s) << endl;
    return 0;
}

Output:

Result: acdb

Explanation:

1. The input string "cbacdcbc" is processed to remove duplicates while ensuring the smallest lexicographical order.

2. The function counts occurrences of each character and uses a stack to maintain the result string.

3. Characters are added to the stack, making sure to pop any characters that can be added later and are greater than the current character.

4. This ensures that the resulting string "acdb" is the smallest lexicographically possible string that can be formed by removing duplicates from the input string.

5. The approach combines greedy algorithm concepts with stack data structure for efficient string manipulation.