Programa Javascript para encontrar la longitud de la substring más larga sin repetir caracteres

Dada una string str , encuentre la longitud de la substring más larga sin repetir caracteres. 

• Para “ABDEFGABEF”, las substrings más largas son “BDEFGA” y “DEFGAB”, con una longitud de 6.
• Para «BBBB», la substring más larga es «B», con una longitud de 1.
• Para «GEEKSFORGEEKS», hay dos substrings más largas que se muestran en los diagramas a continuación, con una longitud de 7

La complejidad de tiempo deseada es O(n) donde n es la longitud de la string.

Método 1 (Simple: O (n ³ )) : Podemos considerar todas las substrings una por una y verificar para cada substring si contiene todos los caracteres únicos o no. Habrá n*(n+1)/2 substrings. Si una substring contiene todos los caracteres únicos o no, se puede verificar en tiempo lineal escaneándola de izquierda a derecha y manteniendo un mapa de los caracteres visitados. La complejidad temporal de esta solución sería O(n^3).

<script>
  
// JavaScript program to find the length of the
// longest substring without repeating
// characters
// This function returns true if all characters in
// str[i..j] are distinct, otherwise returns false
function areDistinct(str, i, j)
{
      
    // Note : Default values in visited are false
    var visited = new [26];
  
    for(var k = i; k <= j; k++)
    {
        if (visited[str.charAt(k) - 'a'] == true)
            return false;
              
        visited[str.charAt(k) - 'a'] = true;
    }
    return true;
}
  
// Returns length of the longest substring
// with all distinct characters.
function longestUniqueSubsttr(str)
{
    var n = str.length();
      
    // Result
    var res = 0; 
      
    for(var i = 0; i < n; i++)
        for(var j = i; j < n; j++)
            if (areDistinct(str, i, j))
                res = Math.max(res, j - i + 1);
                  
    return res;
}
  
// Driver code
    var str = "geeksforgeeks";
    document.write("The input string is " + str);
  
    var len = longestUniqueSubsttr(str);
      
    document.write("The length of the longest " +
                       "non-repeating character " + 
                       "substring is " + len);
  
// This code is contributed by shivanisinghss2110.
  
</script>

The input string is geeksforgeeks
The length of the longest non-repeating character substring is 7

Método 2 (Mejor : O(n ² )) La idea es usar ventana deslizante . Siempre que vemos repetición, eliminamos la ocurrencia anterior y deslizamos la ventana.

<script>
  
// JavaScript program to find the length of the 
// longest substring without repeating
// characters
  
function longestUniqueSubsttr(str)
{
    var n = str.length();
      
    // Result
    var res = 0;
      
    for(var i = 0; i < n; i++)
    {
          
        // Note : Default values in visited are false
        var visited = new [256];
          
        for(var j = i; j < n; j++)
        {
              
            // If current character is visited
            // Break the loop
            if (visited[str.charAt(j)] == true)
                break;
  
            // Else update the result if
            // this window is larger, and mark
            // current character as visited.
            else
            {
                res = Math.max(res, j - i + 1);
                visited[str.charAt(j)] = true;
            }
        }
  
        // Remove the first character of previous
        // window
        visited[str.charAt(i)] = false;
    }
    return res;
}
  
// Driver code
    var str = "geeksforgeeks";
    document.write("The input string is " + str);
  
    var len = longestUniqueSubsttr(str);
    document.write("The length of the longest " +
                       "non-repeating character " +
                       "substring is " + len);
   
// This code is contributed by shivanisinghss2110     
</script>

The input string is geeksforgeeks
The length of the longest non-repeating character substring is 7

Método 4 (Tiempo lineal) : Hablemos ahora de la solución de tiempo lineal. Esta solución utiliza espacio adicional para almacenar los últimos índices de caracteres ya visitados. La idea es escanear la string de izquierda a derecha, realizar un seguimiento de la substring de caracteres no repetidos de longitud máxima vista hasta ahora en res . Cuando recorremos la string, para saber la longitud de la ventana actual necesitamos dos índices. 
1) Índice final ( j ): Consideramos el índice actual como índice final. 
2) Índice inicial ( i ): Es igual que la ventana anterior si el carácter actual no estaba presente en la ventana anterior. Para verificar si el carácter actual estaba presente en la ventana anterior o no, almacenamos el último índice de cada carácter en una array lasIndex[]. Si lastIndex[str[j]] + 1 es más que el inicio anterior, entonces actualizamos el índice de inicio i. De lo contrario, mantenemos el mismo i.  

A continuación se muestra la implementación del enfoque anterior:

<script>
  
// JavaScript program to find the length of the longest substring
// without repeating characters
var NO_OF_CHARS = 256;
  
function longestUniqueSubsttr(str)
    {
        var n = str.length();
  
        var res = 0; // result
  
        // last index of all characters is initialized
        // as -1
        var lastIndex = new [NO_OF_CHARS];
        Arrays.fill(lastIndex, -1);
  
        // Initialize start of current window
        var i = 0;
  
        // Move end of current window
        for (var j = 0; j < n; j++) {
  
            // Find the last index of str[j]
            // Update i (starting index of current window)
            // as maximum of current value of i and last
            // index plus 1
            i = Math.max(i, lastIndex[str.charAt(j)] + 1);
  
            // Update result if we get a larger window
            res = Math.max(res, j - i + 1);
  
            // Update last index of j.
            lastIndex[str.charAt(j)] = j;
        }
        return res;
    }
  
    /* Driver program to test above function */
      
        var str = "geeksforgeeks";
        document.write("The input string is " + str);
        var len = longestUniqueSubsttr(str);
        document.write("The length of the longest non repeating character is " + len);
  
// This code is contributed by shivanisinghss2110
  
</script>

The input string is geeksforgeeks
The length of the longest non-repeating character substring is 7

Complejidad de tiempo: O(n + d) donde n es la longitud de la string de entrada y d es el número de caracteres en el alfabeto de la string de entrada. Por ejemplo, si la string consta de caracteres ingleses en minúsculas, el valor de d es 26. 
Espacio auxiliar: O(d) 

Consulte el artículo completo sobre Longitud de la substring más larga sin repetir caracteres para obtener más detalles.