Mínimo K tal que cada substring de longitud al menos K contiene un carácter c | Conjunto-2

Dada una string S que consiste en N alfabetos ingleses en minúsculas, y también dado que un carácter C se llama K-increíble , si cada substring de longitud al menos K contiene este carácter C, la tarea es encontrar el mínimo K posible tal que exista al menos un personaje K-increíble .

Ejemplos:

Entrada: S = “abcde” 
Salida: 3 
Explicación: 
Cada substring de longitud de al menos 3, tiene un carácter K-asombroso, ‘c’: {“abc”, “bcd”, “cde”, “abcd”, “ bcde”, “abcde”}. 

Entrada: S = “aaaa” 
Salida: 1
Explicación: 
Cada substring de longitud de al menos 1, tiene un carácter K-asombroso, ‘a’: {“a”, “aa”, “aaa”, “aaaa”}. 

Para el enfoque de búsqueda ingenua y binaria, consulte el conjunto 1

Enfoque: el enfoque ingenuo se puede optimizar basándose en la observación de que para que exista un carácter ‘ C ‘ en cada substring de longitud K , la distancia entre las posiciones de dos ‘ C ‘ consecutivas no puede exceder K. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable entera, digamos ans como N , que almacenará el tamaño mínimo posible de la substring, de modo que cada substring de tamaño ans tenga al menos un carácter K-asombroso .
• Inserte el carácter ‘ 0 ‘ al principio y al final de la string S.
• Itere sobre los caracteres en el rango [a, z] usando la variable c y realice los siguientes pasos:
  • Asigne el carácter c a S[0] y S[N+1].
  • Inicialice dos variables, digamos prev como 0 y maxLen como 0, donde prev almacenará el último índice del carácter c y maxLen almacenará la distancia máxima entre las posiciones de los dos c más cercanos .
  • Iterar sobre el rango [1, N+1] usando la variable i y realizar los siguientes pasos:
    • Si S[i] = c, modifique el valor de maxLen   a max(maxLen, i – prev) y luego asigne i a prev .
  • Ahora modifique el valor de ans a min(ans, max_len) .
• Finalmente, después de completar los pasos anteriores, imprima el valor de ans obtenido.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum value of K
// such that there exist atleast one K
// amazing character
 
int MinimumLengthSubstring(string S, int N)
{
    // Stores the answer
    int ans = N;
 
    // Update the string S
    S = "0" + S + "0";
 
    // Iterate over the characters
    // in range [a, z]
    for (char c = 'a'; c <= 'z'; ++c) {
 
        // Stores the last index where
        // c appears
        int prev = 0;
 
        // Stores the maximum possible length
        int max_len = 0;
 
        // Update string S
        S[0] = c;
        S[N + 1] = c;
 
        // Iterate over characters of string
        // S
        for (int i = 1; i <= N + 1; ++i) {
            // If S[i] is equal to c
            if (S[i] == c) {
 
                // Stores the distance between
                // positions of two same c
                int len = i - prev;
 
                // Update max_len
                max_len = max(max_len, len);
 
                // Update the value of prev
                prev = i;
            }
        }
 
        // Update the value of ans
        ans = min(ans, max_len);
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    string S = "abcde";
    int N = S.length();
 
    // Function Call
    cout << MinimumLengthSubstring(S, N);
}

# Python3 program for the above approach
 
# Function to find minimum value of K
# such that there exist atleast one K
# amazing character
def MinimumLengthSubstring(S, N):
     
    # Stores the answer
    ans = N
 
    # Update the S
    S = "0" + S + "0"
    S = [i for i in S]
 
    # Iterate over the characters
    # in range [a, z]
    for c in range(ord('a'), ord('z') + 1):
         
        # Stores the last index where
        # c appears
        prev = 0
 
        # Stores the maximum possible length
        max_len = 0
 
        # Update S
        S[0] = chr(c)
        S[N + 1] = chr(c)
 
        # Iterate over characters of string
        # S
        for i in range(1, N + 2):
             
            # If S[i] is equal to c
            if (S[i] == chr(c)):
                 
                # Stores the distance between
                # positions of two same c
                len = i - prev
 
                # Update max_len
                max_len = max(max_len, len)
 
                # Update the value of prev
                prev = i
 
        # Update the value of ans
        ans = min(ans, max_len)
 
    # Return the answer
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    S = "abcde"
    N = len(S)
 
    # Function Call
    print(MinimumLengthSubstring(S, N))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find minimum value of K
// such that there exist atleast one K
// amazing character
 
static int MinimumLengthSubstring(string S, int N)
{
    // Stores the answer
    int ans = N;
 
    // Update the string S
    S = "0" + S + "0";
 
    // Iterate over the characters
    // in range [a, z]
    for (char c = 'a'; c <= 'z'; ++c) {
 
        // Stores the last index where
        // c appears
        int prev = 0;
 
        // Stores the maximum possible length
        int max_len = 0;
 
        // Update string S
       S = S.Substring(0,0) + c + S.Substring(1);
       S = S.Substring(0, N+1) + c + S.Substring(N + 2);
 
        // Iterate over characters of string
        // S
        for (int i = 1; i <= N + 1; ++i) {
            // If S[i] is equal to c
            if (S[i] == c) {
 
                // Stores the distance between
                // positions of two same c
                int len = i - prev;
 
                // Update max_len
                max_len = Math.Max(max_len, len);
 
                // Update the value of prev
                prev = i;
            }
        }
 
        // Update the value of ans
        ans = Math.Min(ans, max_len);
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void Main()
{
    // Given Input
    string S = "abcde";
    int N = S.Length;
 
    // Function Call
    Console.Write(MinimumLengthSubstring(S, N));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
 
// JavaScript program for the above approach
 
 
// Function to find minimum value of K
// such that there exist atleast one K
// amazing character
 
function MinimumLengthSubstring(S, N) {
    // Stores the answer
    let ans = N;
 
    // Update the string S
    S = "0" + S + "0";
    S = S.split("")
 
    // Iterate over the characters
    // in range [a, z]
    for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); ++c) {
 
        // Stores the last index where
        // c appears
        let prev = 0;
 
        // Stores the maximum possible length
        let max_len = 0;
 
        // Update string S
        S[0] = String.fromCharCode(c);
        S[N + 1] = String.fromCharCode(c);
 
        // Iterate over characters of string
        // S
        for (let i = 1; i <= N + 1; ++i) {
            // If S[i] is equal to c
            if (S[i] == String.fromCharCode(c)) {
 
                // Stores the distance between
                // positions of two same c
                let len = i - prev;
 
                // Update max_len
                max_len = Math.max(max_len, len);
 
                // Update the value of prev
                prev = i;
            }
        }
 
        // Update the value of ans
        ans = Math.min(ans, max_len);
    }
 
    // Return the answer
    return ans;
}
 
 
 
 
// Driver Code
 
// Given Input
let S = "abcde";
let N = S.length;
 
// Function Call
document.write(MinimumLengthSubstring(S, N));
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)