Rechercher la plus grande sous-chaîne contenant un nombre égal de 0 et de 1 dans une chaîne binaire

Ce qui suit fonctionnera dans le temps et l'espace O (n) , n étant le nombre de caractères de la chaîne.

• garder une trace du solde actuel (ou du déséquilibre) de 1 et 0 que vous avez vu dans la chaîne code> et la première fois où la chaîne a le même solde (un tableau ou une carte avec au plus n entrées)
• itérer la chaîne , et pour chaque caractère ...
  • mettre à jour le solde , en comptant "1" comme 1 et "0" comme - 1 ou vice versa
  • vérifier quand, le cas échéant, vous avez rencontré le même solde avant
  • si la différence est supérieure au meilleur actuel, souvenez-vous de la nouvelle sous-chaîne la plus longue
  • si vous n'avez pas encore rencontré ce solde, rappelez-vous qu'il s'agit de la première position actuelle

Exemple de code en Python:

0 1 1  {0: 0, 1: 1}
1 0 0 10 {0: 0, 1: 1}
2 1 1 10 {0: 0, 1: 1}
3 0 0 1010 {0: 0, 1: 1}
4 1 1 1010 {0: 0, 1: 1}
5 1 2 1010 {0: 0, 1: 1, 2: 6}
6 1 3 1010 {0: 0, 1: 1, 2: 6, 3: 7}
7 0 2 1010 {0: 0, 1: 1, 2: 6, 3: 7}
8 0 1 01011100 {0: 0, 1: 1, 2: 6, 3: 7}
9 0 0 1010111000 {0: 0, 1: 1, 2: 6, 3: 7}

Sortie:

string = "1010111000"
first = {0: 0}  # map or array; 0th element is 0
balance = 0     # initially, 1 and 0 are balanced
best = ""       # best substring found
for i, c in enumerate(string):             # (i, c) = (index, character)
    balance += 1 if c == "1" else -1       # update balance
    if balance not in first:               # first time we see this balance?
        first[balance] = i+1               # add next(!) position to map/array
    elif i - first[balance] > len(best):   # otherwise, if new longest substring
        best = string[first[balance]:i+1]  # update best with slice of string
    print(i, c, balance, best, first)      # debugging/demo output

Je l'aborderais comme ça

• Initialise une somme entière variable et maxlength = minimum

• Définissez un hashmap avec avec sum comme clé et index comme valeur

• Pour chaque valeur de la chaîne donnée

  • somme + = arr [i] == 0? puis ajoutez -1 sinon ajoutez un 1

  • si la somme est 0 maxlength = maxlength ou index + 1 puisqu'il s'agit d'une réponse potentielle

  • sinon si le dictionnaire contient cette valeur de somme, maxlength = maxlength ou (i -index hash [sum]) la valeur de la somme trouvée précédemment contribuant au résultat.

  • met à jour la table de hachage si la valeur de sum n'est pas dans la carte de hachage avec index

  • renvoie la longueur maximale.

Voici un exemple de ce que j'ai mentionné ci-dessus, dans le code: exemple fonctionnel vous pouvez essayer de changer le cas de test pour voir comment cela fonctionnerait pour différents cas de test, essayez également d'imprimer la carte de hachage et de la tracer à la main pour mieux comprendre.

Cette solution n'est pas la meilleure en termes d'optimisation, mais dans la précipitation et le stress d'une interview, celle-ci peut être rapidement pensée, dessinée et expliquée.

Je nicherais 2 boucles. p >

1 de 0 à len - 2 (incrémentation) (la longueur minimale doit être de 2)

1 à partir de len à la valeur de boucle précédente + 2 (décrémentation) (la longueur minimale doit être de 2 )

Récupère la sous-chaîne des itérateurs correspondants des boucles

Compter si les caractères sont égaux.

alors, si vrai, comparer avec la longueur du résultat stocké, si la longueur est supérieure, écrasez le résultat.

En utilisant 0100 comme exemple, cela testera par rapport à ces valeurs:

var iterations = 0;

function IsBalanced(input, char1, char2)
{
    if (input.length % 2 != 0) // odd length can't be balanced
    {
      ++iterations;
      return (false);
    }
    let char1count = 0;
    let char2count = 0;
    let len = input.length;
    for (let i = 0; i < len; ++i)
    {
        ++iterations;
        if (input[i] == char1)
            ++char1count;
        else
            ++char2count;
    }
    return (char1count == char2count);
}

function findLargest(input, char1, char2)
{
    let len = input.length;
    let result = '';
    for (let k = 0; k < len - 1; ++k)
    {
        //        This is a tweak to reduce the number of iterations
        //  To avoid testing a substring smaller than the current result
        //                           |
        //                           |
        //                v----------------------v
        for (let l = len; l - k > result.length && l > k + 1; --l)
        {
            tempResult = input.substring(k, l);
            if (IsBalanced(tempResult, char1, char2) && tempResult.length > result.length)
                result = tempResult;
        }
    }
    return (result);
}

console.log("Input : 1010111 - result : " + findLargest("1010111", "1", "0") + " original size : " + "1010111".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : ababaaa - result : " + findLargest("ababaaa", "a", "b") + " original size : " + "ababaaa".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 00100100 - result : " + findLargest("00100100", "1", "0") + " original size : " + "00100100".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 1111100000 - result : " + findLargest("1111100000", "1", "0") + " original size : " + "1111100000".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 0001111111111010001111100000000001111111111 - result : " + findLargest("0001111111111010001111100000000001111111111", "1", "0") + " original size : " + "0001111111111010001111100000000001111111111".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 0000000000000000000000000000000000000000000000000001 - result : " + findLargest("0000000000000000000000000000000000000000000000000001", "1", "0") + " original size : " + "0000000000000000000000000000000000000000000000000001".length + " - iterations : " + iterations);

Exemple JavaScript (je l'ai un peu modifié pour optimiser le nombre d'itérations, mais l'approche est la même):

// result = ''
0100 //not balanced
010  //not balanced
01   //balanced AND length is greated than result's one. result = '01'
 100 //not balanced
 10  //balanced BUT length is not greated than result's one
  00 //not balanced