A substring mais longa do Leetcode sem repetir caracteres

Question

Link aqui Estou atualmente aprendendo c ++ vindo de um plano de fundo de python, então incluirei uma solução em python e em c ++ para a seguinte declaração de problema e com base nas respostas muito úteis obtidas em minha pergunta anterior , fiz algumas melhorias na implementação de c ++ :

Dada uma string s, encontre o comprimento da substring mais longa sem repetir caracteres.

Exemplo 1:

Entrada: s = "abcabcbb" Saída: 3

Exemplo 2:

Entrada: s = "bbbbb" Saída: 1

Eu gostaria de melhorar a velocidade das implementações de python e c ++, e preciso melhorar o consumo de memória na implementação de c ++, pois obtive um número muito alto (600+ MB), bem como as razões para esse alto consumo (se o número for preciso), e também gostaria de sugestões gerais.

longest_substring.py

def get_longest(s: str):
    possibilities = (s[i:] for i in range(len(s)))
    maximum = 0
    for possibility in possibilities:
        end_idx = maximum
        while end_idx <= len(possibility):
            current_chunk = possibility[0:end_idx]
            end_idx += 1
            if not (current_size := len(current_chunk)) == len(set(current_chunk)):
                break
            maximum = max(current_size, maximum)
    return maximum


if __name__ == '__main__':
    print(f'Longest substring:\n{get_longest("abcabcbb")}')

Estatísticas Leetcode:

Tempo de execução: 260 ms, mais rápido do que 19,36% das submissões online do Python3 para caracteres mais longos de substring sem repetição.

Uso de memória: 14,4 MB, menos de 100,00% dos envios online do Python3 para caracteres mais longos de substring sem repetição.

longest_substring.h

#ifndef LEETCODE_LONGEST_SUBSTRING_H
#define LEETCODE_LONGEST_SUBSTRING_H

#include <string>

int longest_sub(const std::string &s);
bool check_unique(const std::string &s);

#endif //LEETCODE_LONGEST_SUBSTRING_H

longest_substring.cpp

#include "longest_substring.h"
#include <iostream>
using std::endl;
using std::cout;
using std::string;


bool check_unique(const string &s) {
    for (size_t i = 0; i < s.size() - 1; ++i) {
        for (size_t j = i + 1; j < s.size(); ++j) {
            if (s[i] == s[j])
                return false;
        }
    }
    return true;
}


int longest_sub(const string &s) {
    int maximum = 0;
    for (size_t i = 0; i < s.size(); ++i) {
        const string possibility = s.substr(i);
        auto end_idx = maximum;
        while (end_idx < possibility.size()) {
            const string current_chunk = possibility.substr(0, ++end_idx);
            if (!check_unique(current_chunk))
                break;
            auto current_size = current_chunk.size();
            if (current_size > maximum)
                maximum = current_size;
        }
    }
    return maximum;
}


int main() {
    cout << "Longest substring: " << endl;
    cout << longest_sub("abcabcbb");
}

Estatísticas Leetcode:

Tempo de execução: 100 ms, mais rápido do que 14,88% dos envios online C ++ para caracteres mais longos de substring sem repetição.

Uso de memória: 604,2 MB, menos de 5,02% dos envios online C ++ para caracteres mais longos de substring sem repetição.

Answer 1

Complexidade

Sua solução tem complexidade de tempo \$\mathcal{O}(N^4)\$, o que é muito ruim. Há um \$\mathcal{O}(N)\$solução para este problema. Considere, por exemplo, a string:

abcdecfghij

Em vez de pegar substrings e verificar se a substring tem duplicatas, mantenha o controle da última posição vista para qualquer caractere possível. Este é basicamente um array de 256 ints, que você deve inicializar com -1 para indicar que nunca viu o caractere antes. Em seguida, itere sobre a string caractere por caractere e verifique se o caractere que você está examinando já foi visto. Caso contrário, atualize sua posição na matriz. Então, após o processamento abcde, você terá a = 0, b = 1, c = 2, d = 3, e = 4e o resto está quieto -1. Então, quando você se encontrar cnovamente, você sabe que tem uma duplicata. Mas em vez de começar do segundo caractere da string, você deve começar a partir do caractere logo após o primeiro c, então na posição 3. E você sabe que já tem uma substring válida até e incluindo o segundo c. Então você pode continuar a partir daí. Você continua até encontrar um caractere com uma posição registrada que é igual ou maior que a posição inicial da substring atual. Aqui está uma possível implementação em C ++:

#include <array>
#include <utility>

int longest_sub(const std::string &s) {
    std::array<int, 256> last_positions;
    last_positions.fill(-1);

    int min_position = 0;
    int maximum_length = 0;

    for (size_t i = 0; i < s.size(); ++i) {
        int &last_position = last_positions[static_cast<unsigned char>(s[i])];

        if (last_position >= min_position) {
            // We encountered a duplicate
            min_position = last_position + 1;
        }

        maximum_length = std::max(maximum_length, int(i + 1 - min_position));
        last_position = i;
    }

    return maximum_length;
}

Answer 2

G. Sliepen já cuidou das questões gerais , onde você obtém o melhor retorno do investimento.

Ainda assim, existem alguns problemas com o código, além do uso de um algoritmo abaixo do ideal:

1. Você deve considerar std::string_viewpara o argumento string e para obter uma fatia temporária de uma string de longa duração.
   A alocação dinâmica é muito cara e deve ser evitada, tanto ao chamar uma função se a entrada não estiver no formato desejado, quanto na própria função.
   Consulte “ O que é string_view? ” E “ Como exatamente é std::string_viewmais rápido do que const std::string&? ” Para obter mais detalhes.

2. Agora que as funções não alocam mais memória ou contêm qualquer outro potencial lançador de exceções, marque-as noexceptpara que todos saibam (e o compilador reforça) que não serão lançadas. Não fará muita coisa aqui, mas é uma boa documentação, informa ao compilador se ele apenas conhece a declaração, e pode ser importante posteriormente com o uso de código-modelo consumindo-o para melhor desempenho e maiores garantias de segurança de exceção.

3. Além disso, marque-os constexprenquanto estiver fazendo isso, para permitir o uso em expressão constante e encorajar a avaliação em tempo de compilação. Essa também é uma prática recomendada, não mudando muito de nada em seu próprio programa de exemplo.

4. Você usa std::coutduas vezes (por que você não coloca toda a saída nele em uma única expressão, não me lembro, mas isso pode ser argumentado de qualquer maneira) e std::endluma vez. Escrever (e manter em mente) essas duas declarações de uso custa mais do que prefixar os usos com std::. Mesmo que você realmente não goste de escrever std::, você não escreve com menos frequência.

5. Não force a descarga de um córrego, a menos que seja realmente sincero, pois isso esvazia o desempenho. std::endlgera uma nova linha e depois esvazia, stream << std::endlsendo exatamente equivalente a stream << '\n' << std::flush. Portanto, se você realmente precisa, é melhor ser explícito e usar std::flush.
   Consulte " O que é o endlfiasco do C ++ iostream ? " Para obter mais detalhes.