Remove Duplicate Letters

Enunciado do problema

Dada uma string que contém apenas letras minúsculas, remova as letras duplicadas para que cada letra apareça uma vez e somente uma vez. Você deve certificar-se de que seu resultado é o menor em ordem lexicográfica entre todos os resultados possíveis e que a posição das letras é mantido.

Solução

Para resolver esse problema, primeiramente vamos contar a frequência de cada caractere no texto de entrada. Isso irá nos auxiliar na tomada de decisão quando estivermos montando a nova palavra com apenas os caracteres distinto na ordem lexicográfica.

Após a contagem vamos definir de maneira gulosa se colocamos a letra na nossa string resultado ou não. Para isso vamos ter também um vetor onde iremos identificar se uma letra foi usada ou não na formação da nossa string de resultados.

Cada vez que um novo caractere for processado primeiro vamos reduzir 1 ao vetor que guarda a frequência de caracteres, pois acabamos de processar um e não temos ele mais como disponível. Se esse caractere já tiver sido utilizado na formação da palavra final, apenas continuamos para a próxima iteração. Em caso negativo nós temos que verificar três condições:

Enquanto todas essas condições forem positivas nós vamos remover a última letra do resultado e marcar ela como não utilizada no nosso vetor de utilizados. Quando o loop terminar nós adicionamos a letra que estamos processando no final da palavra resultado e marcamos ela como utilizada.

string removeDuplicateLetters(string text){
    string result;
    if(text.empty())
        return result;

    vector<int> count(26,0);
    for(auto c: text){
        count[c-'a']++;
    }

    vector<bool> used(26,false);
    for(auto c: text){
        count[c-'a']--;
        if(used[c-'a'])
            continue;
        
        while(!result.empty() && c<result.back() && count[result.back()]>0){
            used[result.back()-'a']=false;
            result.pop_back();
        }

        result+=c;
        used[c-'a'] = true;
    }

    return result;
}

Complexidade de tempo: O(n)

Complexidade de espaço: O(n)

question from LeetCode