Remove Duplicate Letters

                                            
class Solution {
public:
    string removeDuplicateLetters(string s) {
        string ans;
        vector<int> count(26); // count frequency of each character
        vector<bool> visited(26); // check if character is already in answer
        
        for(char c : s) {
            count[c - 'a']++;
        }
        
        for(char c : s) {
            count[c - 'a']--;
            
            if(visited[c - 'a']) {
                continue;
            }
            
            while(!ans.empty() && ans.back() > c && count[ans.back() - 'a'] > 0) {
                visited[ans.back() - 'a'] = false;
                ans.pop_back();
            }
            
            ans.push_back(c);
            visited[c - 'a'] = true;
        }
        
        return ans;
    }
};

                                            
class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        int[] count = new int[256];
        boolean[] visited = new boolean[256];

        for (char c : s.toCharArray()) {
            count[c]++;
        }

        for (char c : s.toCharArray()) {
            count[c]--;

            if (visited[c]) {
                continue;
            }

            while (!stack.isEmpty() && stack.peek() > c && count[stack.peek()] > 0) {
                visited[stack.pop()] = false;
            }

            stack.push(c);
            visited[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (char c : stack) {
            sb.append(c);
        }

        return sb.toString();
    }
}

                                            
class Solution(object):
    def removeDuplicateLetters(self, s):
        stack = []
        counter = collections.Counter(s)
        visited = set()
        
        for char in s:
            counter[char] -= 1
            if char in visited:
                continue
            
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                visited.remove(stack.pop())
            
            stack.append(char)
            visited.add(char)
        
        return ''.join(stack)

                                            
char* removeDuplicateLetters(char* s) {
    char *result = calloc(27, sizeof(char));
    int count[26] = {0};
    bool visited[26] = {false};
    
    for(int i = 0; i < strlen(s); i++) {
        count[s[i] - 'a']++;
    }
    
    int index = 0;
    for(int i = 0; i < strlen(s); i++) {
        count[s[i] - 'a']--;
        if(visited[s[i] - 'a']) {
            continue;
        }
        
        while(index > 0 && s[i] < result[index - 1] && count[result[index - 1] - 'a'] > 0) {
            visited[result[index - 1] - 'a'] = false;
            index--;
        }
        
        result[index++] = s[i];
        visited[s[i] - 'a'] = true;
    }
    
    result[index] = '\0';
    return result;
}

                                            
public class Solution {
    public string RemoveDuplicateLetters(string s) {
        if (string.IsNullOrEmpty(s))
            return string.Empty;
        
        int[] count = new int[26];
        bool[] visited = new bool[26];
        StringBuilder sb = new StringBuilder();
        
        foreach (char c in s)
            count[c - 'a']++;
        
        foreach (char c in s)
        {
            count[c - 'a']--;
            if (visited[c - 'a'])
                continue;
            
            while (sb.Length > 0 && sb[sb.Length - 1] > c && count[sb[sb.Length - 1] - 'a'] > 0)
            {
                visited[sb[sb.Length - 1] - 'a'] = false;
                sb.Remove(sb.Length - 1, 1);
            }
            sb.Append(c);
            visited[c - 'a'] = true;
        }
        
        return sb.ToString();
    }
}

                                            
/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
    const stack = [];
    const count = new Array(26).fill(0);
    const visited = new Array(26).fill(false);

    for (let char of s) {
        count[char.charCodeAt(0) - 97]++;
    }

    for (let char of s) {
        count[char.charCodeAt(0) - 97]--;

        if (visited[char.charCodeAt(0) - 97]) {
            continue;
        }

        while (stack.length > 0 && stack[stack.length - 1] > char && count[stack[stack.length - 1].charCodeAt(0) - 97] > 0) {
            visited[stack.pop().charCodeAt(0) - 97] = false;
        }

        stack.push(char);
        visited[char.charCodeAt(0) - 97] = true;
    }

    return stack.join('');
};

                                            
function removeDuplicateLetters(s: string): string {
    const lastSeen: {[key: string]: number} = {};
    const stack: string[] = [];
    const seen: Set<string> = new Set();

    for (let i = 0; i < s.length; i++) {
        lastSeen[s[i]] = i;
    }

    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (!seen.has(char)) {
            while (stack.length > 0 && stack[stack.length - 1] > char && i < lastSeen[stack[stack.length - 1]]) {
                const top = stack.pop();
                seen.delete(top);
            }
            stack.push(char);
            seen.add(char);
        }
    }

    return stack.join('');
};

                                            
class Solution {
    /**
     * @param String $s
     * @return String
     */
    function removeDuplicateLetters($s) {
        $stack = [];
        $seen = [];
        $lastOccur = [];
        
        for ($i = 0; $i < strlen($s); $i++) {
            $lastOccur[ord($s[$i]) - ord('a')] = $i;
        }
        
        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (!in_array($char, $seen)) {
                while (!empty($stack) && end($stack) > $char && $i < $lastOccur[ord(end($stack)) - ord('a')]) {
                    array_pop($stack);
                    array_pop($seen);
                }
                $stack[] = $char;
                $seen[] = $char;
            }
        }
        
        return implode("", $stack);
    }
}

                                            
class Solution {
    func removeDuplicateLetters(_ s: String) -> String {
        var stack = [Character]()
        var seen = Set<Character>()
        var lastOccurrence = [Character: Int]()
        
        for (index, char) in s.enumerated() {
            lastOccurrence[char] = index
        }
        
        for (index, char) in s.enumerated() {
            if !seen.contains(char) {
                while let lastChar = stack.last, char < lastChar, index < lastOccurrence[lastChar]! {
                    seen.remove(lastChar)
                    stack.removeLast()
                }
                seen.insert(char)
                stack.append(char)
            }
        }
        
        return String(stack)
    }
}

                                            
class Solution {
    fun removeDuplicateLetters(s: String): String {
        val stack = mutableListOf<Char>()
        val count = IntArray(26)
        val visited = BooleanArray(26)
        
        for (c in s) {
            count[c - 'a']++
        }
        
        for (c in s) {
            count[c - 'a']--
            if (visited[c - 'a']) {
                continue
            }
            
            while (stack.isNotEmpty() && stack.last() > c && count[stack.last() - 'a'] > 0) {
                visited[stack.last() - 'a'] = false
                stack.removeAt(stack.size - 1)
            }
            
            stack.add(c)
            visited[c - 'a'] = true
        }
        
        return stack.joinToString("")
    }
}

                                            
class Solution {
  String removeDuplicateLetters(String s) {
    List<int> count = List.filled(26, 0);
    List<bool> used = List.filled(26, false);
    List<String> stack = [];

    for (int i = 0; i < s.length; i++) {
      count[s.codeUnitAt(i) - 'a'.codeUnitAt(0)]++;
    }

    for (int i = 0; i < s.length; i++) {
      count[s.codeUnitAt(i) - 'a'.codeUnitAt(0)]--;
      if (used[s.codeUnitAt(i) - 'a'.codeUnitAt(0)]) {
        continue;
      }

      while (stack.isNotEmpty &&
          s.codeUnitAt(i) < stack.last.codeUnitAt(0) &&
          count[stack.last.codeUnitAt(0) - 'a'.codeUnitAt(0)] > 0) {
        used[stack.last.codeUnitAt(0) - 'a'.codeUnitAt(0)] = false;
        stack.removeLast();
      }

      stack.add(s[i]);
      used[s.codeUnitAt(i) - 'a'.codeUnitAt(0)] = true;
    }

    return stack.join();
  }
}

                                            
func removeDuplicateLetters(s string) string {
    lastOccur := make(map[byte]int)
    for i, char := range s {
        lastOccur[byte(char)] = i
    }
    
    stack := make([]byte, 0)
    seen := make(map[byte]bool)
    
    for i, char := range s {
        b := byte(char)
        if _, ok := seen[b]; !ok {
            for len(stack) > 0 && b < stack[len(stack)-1] && lastOccur[stack[len(stack)-1]] > i {
                delete(seen, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            seen[b] = true
            stack = append(stack, b)
        }
    }
    
    return string(stack)
}

                                            
# @param {String} s
# @return {String}
def remove_duplicate_letters(s)
    stack = []
    seen = {}
    last_occurrence = {}

    s.each_char.with_index do |char, index|
        last_occurrence[char] = index
    end

    s.each_char.with_index do |char, index|
        next if seen[char]

        while !stack.empty? && char < stack.last && last_occurrence[stack.last] > index
            seen[stack.pop] = false
        end

        stack.push(char)
        seen[char] = true
    end

    stack.join
end

                                            
impl Solution {
    pub fn remove_duplicate_letters(s: String) -> String {
        let mut stack: Vec<char> = Vec::new();
        let mut seen: [bool; 26] = [false; 26];
        let mut last_occurrence: [usize; 26] = [0; 26];

        for (i, c) in s.chars().enumerate() {
            last_occurrence[c as usize - 'a' as usize] = i;
        }

        for (i, c) in s.chars().enumerate() {
            if !seen[c as usize - 'a' as usize] {
                while !stack.is_empty() && c < *stack.last().unwrap() && last_occurrence[*stack.last().unwrap() as usize - 'a' as usize] > i {
                    seen[*stack.last().unwrap() as usize - 'a' as usize] = false;
                    stack.pop();
                }
                stack.push(c);
                seen[c as usize - 'a' as usize] = true;
            }
        }

        stack.iter().collect()
    }
}

To solve this coding challenge, you need to remove duplicate letters from a given string

s

such that every letter appears only once and the resultant string is the smallest possible in lexicographical order. Let's dissect and understand the steps thoroughly.

Explanation

Problem Breakdown:

The essence of the problem lies in maintaining a sequence of characters where:

Each character appears only once.
The resultant sequence is the smallest possible when compared dictionary-wise to any other possible combinations.

Constraints and Considerations:

Input consists solely of lowercase English letters.
Ensure all input constraints are considered, especially the maximum length of the string which is 10,000.

Strategy:

The approach leverages a stack to build the result string while ensuring the conditions above are met. The stack helps maintain the order of the characters, and we utilize additional data structures to manage counts and checks:

A counter to track the remaining occurrences of each character in the string.
A set to keep track of characters already present in the resultant stack to avoid duplicates.

Process Flow:

Iterate through each character in the string.
Decrement the count of the current character in the counter as it gets processed.
If the character is already added to the stack (checked via a set), continue to the next character.
Maintain the stack such that the characters are in the smallest lexicographical order by comparing and potentially removing elements in the stack based on the remaining counts.
Append the current character to the stack and mark it as visited.
Construct the result string by joining the elements of the stack.

Detailed Steps in Pseudocode:

Initialize a stack to keep the resultant characters.
Initialize a counter to count character occurrences in the input string.
Initialize a set to keep track of characters currently in the stack.
Loop through each character in the input string:

Decrement the character count in the counter.
If the character is already visited, skip to the next character.
While the current character is smaller than the character at the top of the stack and the top character appears later in the string too, pop the stack.

Remove the popped character from the visited set.

Add the current character to the stack and mark it as visited.

Return the joined stack as the resultant string.

Pseudocode:

Main function to remove duplicate letters and ensure the smallest lexicographical order

                                            
# Function definition to remove duplicate letters while maintaining lexicographical order
Function removeDuplicateLetters(string input_string):
    Initialize stack as an empty list # Stack to build the result
    Initialize counter as a dictionary with character counts of input_string # Track remaining characters
    Initialize visited as an empty set # Track characters in the stack
    
    # Loop through each character in the string
    For each character in input_string:
        Decrement counter[character] by 1 # One less occurrence left
        
        # Skip if character is already in the stack
        If character in visited:
            Continue to the next iteration
        
        # Maintain lexicographical order by comparison and popping
        While stack is not empty AND character < top of stack AND counter[top of stack] > 0:
            Pop the top of stack
            Remove the popped character from visited
            
        # Append current character to stack and mark as visited
        Append character to stack
        Add character to visited
    
    # Return the stack as a joined string
    Return join the stack to form the resultant string

Detailed Steps:

Initialize necessary structures (stack, counter, set).
Loop through each character, adjust the character count.
Ensure characters already visited are skipped.
Utilize the stack for maintaining the lexicographical order by selectively removing characters based on comparisons and remaining counts.
Finally, return the constructed string by joining elements in the stack.

This method ensures the smallest lexicographical sequence where each letter appears once. By leveraging data structures efficiently, we achieve an optimal solution, satisfying the problem constraints effectively.