Mínimo K tal que cada substring de longitud al menos K contiene un carácter c – Part 1

Dada una string S que contiene letras latinas en minúsculas. Un carácter c se llama K-asombroso si cada substring de S con una longitud de al menos K contiene este carácter c. Encuentre el K mínimo posible tal que exista al menos un carácter K-asombroso.
Ejemplos: 
 

Entrada: S = “abcde” 
Salida:
Explicación: cada substring de longitud de al menos 3 contiene el carácter ‘c’, es decir, 
{“abc”, “bcd”, “cde”, “abcd”, “bcde”, “abcde”} 
Entrada: S = “aaaa” 
Salida: 1

Prerrequisitos: solución ingenua de búsqueda binaria : un enfoque simple es iterar sobre todas las longitudes posibles de substrings, es decir, de 1 a N (tamaño de la string) y para cada substring de longitud actual, compruebe si aparece algún carácter en todas esas substrings. Solución eficiente: la idea clave es realizar una búsqueda binaria sobre la respuesta K , ya que si algún carácter c aparece en todas las substrings de longitud X , siempre aparecerá en todas las substrings de longitud (X + 1)

. Por lo tanto, podemos verificar la longitud actual e intentar minimizarla usando el algoritmo divide y vencerás. Para verificar si algún carácter aparece en todas las substrings de longitud X, itere sobre todos los caracteres de ‘a’ a ‘z’ y dentro de otro ciclo almacene iterativamente la última aparición del último carácter. 
Deje que la posición actual sea j, por lo que la última substring de longitud X será de (j – X) a X. Compruebe si la posición de la última aparición del carácter K-asombroso actual es mayor que (j – X) o no. Si es mayor, entonces esa substring es una string válida.
A continuación se muestra la implementación del enfoque anterior. 
 

C++

// CPP Program to find minimum K such that
// every substring of length atleast K
// contains some character c
#include <bits/stdc++.h>
using namespace std;
 
// This function checks if there exists some
// character which appears in all K length
// substrings
int check(string s, int K)
{
    // Iterate over all possible characters
    for (int ch = 0; ch < 26; ch++) {
        char c = 'a' + ch;
 
        // stores the last occurrence
        int last = -1;
 
        // set answer as true;
        bool found = true;
        for (int i = 0; i < K; i++)
            if (s[i] == c)
                last = i;
 
        // No occurrence found of current
        // character in first substring
        // of length K
        if (last == -1)
            continue;
 
        // Check for every last substring
        // of length K where last occurr-
        // ence exists in substring
        for (int i = K; i < s.size(); i++) {
            if (s[i] == c)
                last = i;
 
            // If last occ is not
            // present in substring
            if (last <= (i - K)) {
                found = false;
                break;
            }
        }
        // current character is K amazing
        if (found)
            return 1;
    }
    return 0;
}
 
// This function performs binary search over the
// answer to minimise it
int binarySearch(string s)
{
    int low = 1, high = (int)s.size();
    int ans;
    while (low <= high) {
        int mid = (high + low) >> 1;
 
        // Check if answer is found try
        // to minimise it
        if (check(s, mid)) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    return ans;
}
 
// Driver Code to test above functions
int32_t main()
{
    string s = "abcde";
    cout << binarySearch(s) << endl;
 
    s = "aaaa";
    cout << binarySearch(s) << endl;
    return 0;
}

Java

// Java Program to find minimum K such that
// every substring of length atleast K
// contains some character c
 
class GFG
{
     
         
        // This function checks if there exists some
        // character which appears in all K length
        // substrings
        static int check(String s, int K)
        {
            // Iterate over all possible characters
            for (int ch = 0; ch < 26; ch++) {
                char c = (char)( 'a' + ch);
         
                // stores the last occurrence
                int last = -1;
         
                // set answer as true;
                boolean found = true;
                for (int i = 0; i < K; i++)
                    if (s.charAt(i) == c)
                        last = i;
         
                // No occurrence found of current
                // character in first substring
                // of length K
                if (last == -1)
                    continue;
         
                // Check for every last substring
                // of length K where last occurr-
                // ence exists in substring
                for (int i = K; i < s.length(); i++) {
                    if (s.charAt(i) == c)
                        last = i;
         
                    // If last occ is not
                    // present in substring
                    if (last <= (i - K)) {
                        found = false;
                        break;
                    }
                }
                // current character is K amazing
                if (found)
                    return 1;
            }
            return 0;
        }
         
        // This function performs binary search over the
        // answer to minimise it
        static int binarySearch(String s)
        {
            int low = 1, high = s.length();
            int ans=0;
            while (low <= high) {
                int mid = (high + low) >> 1;
         
                // Check if answer is found try
                // to minimise it
                if (check(s, mid)==1) {
                    ans = mid;
                    high = mid - 1;
                }
                else
                    low = mid + 1;
            }
            return ans;
        }
         
        // Driver Code to test above functions
        public static void main(String args[])
        {
            String s = "abcde";
            System.out.println(binarySearch(s));
         
            s = "aaaa";
            System.out.println(binarySearch(s));
     
        }
 
}
 
// This article is contributed
// by ihritik

Python3

# Python3 Program to find minimum K such
# that every substring of length atleast
# K contains some character c
 
# This function checks if there exists
# some character which appears in all
# K length substrings
def check(s, K):
 
    # Iterate over all possible characters
    for ch in range(0, 26):
        c = chr(97 + ch) # Ascii value of 'a' => 97
 
        # stores the last occurrence
        last = -1
 
        # set answer as true
        found = True
        for i in range(0, K):
            if s[i] == c:
                last = i
 
        # No occurrence found of current character
        # in first substring of length K
        if last == -1:
            continue
 
        # Check for every last substring
        # of length K where last occurr-
        # ence exists in substring
        for i in range(K, len(s)):
            if s[i] == c:
                last = i
 
            # If last occ is not
            # present in substring
            if last <= (i - K):
                found = False
                break
             
        # current character is K amazing
        if found:
            return 1
     
    return 0
 
# This function performs binary search
# over the answer to minimise it
def binarySearch(s):
 
    low, high, ans = 1, len(s), None
     
    while low <= high:
        mid = (high + low) >> 1
 
        # Check if answer is found
        # try to minimise it
        if check(s, mid):
            ans, high = mid, mid - 1
         
        else:
            low = mid + 1
     
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    s = "abcde"
    print(binarySearch(s))
 
    s = "aaaa"
    print(binarySearch(s))
 
# This code is contributed by Rituraj Jain

C#

// C# Program to find minimum K such that
// every substring of length atleast K
// contains some character c
 
using System;
class GFG
{
     
         
        // This function checks if there exists some
        // character which appears in all K length
        // substrings
        static int check(String s, int K)
        {
            // Iterate over all possible characters
            for (int ch = 0; ch < 26; ch++) {
                char c = (char)( 'a' + ch);
         
                // stores the last occurrence
                int last = -1;
         
                // set answer as true;
                bool found = true;
                for (int i = 0; i < K; i++)
                    if (s[i] == c)
                        last = i;
         
                // No occurrence found of current
                // character in first substring
                // of length K
                if (last == -1)
                    continue;
         
                // Check for every last substring
                // of length K where last occurr-
                // ence exists in substring
                for (int i = K; i < s.Length; i++) {
                    if (s[i] == c)
                        last = i;
         
                    // If last occ is not
                    // present in substring
                    if (last <= (i - K)) {
                        found = false;
                        break;
                    }
                }
                // current character is K amazing
                if (found)
                    return 1;
            }
            return 0;
        }
         
        // This function performs binary search over the
        // answer to minimise it
        static int binarySearch(String s)
        {
            int low = 1, high = s.Length;
            int ans=0;
            while (low <= high) {
                int mid = (high + low) >> 1;
         
                // Check if answer is found try
                // to minimise it
                if (check(s, mid)==1) {
                    ans = mid;
                    high = mid - 1;
                }
                else
                    low = mid + 1;
            }
            return ans;
        }
         
        // Driver Code to test above functions
        public static void Main()
        {
            String s = "abcde";
            Console.WriteLine(binarySearch(s));
         
            s = "aaaa";
            Console.WriteLine(binarySearch(s));
     
        }
 
}
 
// This article is contributed
// by ihritik

PHP

<?php
// Php Program to find minimum K such that
// every substring of length atleast K
// contains some character c
 
// This function checks if there exists some
// character which appears in all K length
// substrings
function check($s, $K)
{
    // Iterate over all possible characters
    for ($ch = 0; $ch < 26; $ch++)
    {
        $c = chr(ord('a') + $ch) ;
 
        // stores the last occurrence
        $last = -1;
 
        // set answer as true;
        $found = true;
        for ($i = 0; $i < $K; $i++)
            if ($s[$i] == $c)
                $last = $i;
 
        // No occurrence found of current
        // character in first substring
        // of length K
        if ($last == -1)
            continue;
 
        // Check for every last substring
        // of length K where last occurr-
        // ence exists in substring
        for ($i = $K; $i < strlen($s); $i++)
        {
            if ($s[$i] == $c)
                $last = $i;
 
            // If last occ is not
            // present in substring
            if ($last <= ($i - $K))
            {
                $found = false;
                break;
            }
        }
         
        // current character is K amazing
        if ($found)
            return 1;
    }
    return 0;
}
 
// This function performs binary search
// over the answer to minimise it
function binarySearch($s)
{
    $low = 1 ;
    $high = strlen($s) ;
    while ($low <= $high)
    {
        $mid = ($high + $low) >> 1;
 
        // Check if answer is found try
        // to minimise it
        if (check($s, $mid))
        {
            $ans = $mid;
            $high = $mid - 1;
        }
        else
            $low = $mid + 1;
    }
    return $ans;
}
 
// Driver Code
$s = "abcde";
echo binarySearch($s) . "\n";
 
$s = "aaaa";
echo binarySearch($s) . "\n";
 
// This code is contributed by Ryuga
?>

Javascript

<script>
 
// Javascript Program to find minimum K such that
// every substring of length atleast K
// contains some character c
 
// This function checks if there exists some
// character which appears in all K length
// substrings
function check(s, K)
{
    // Iterate over all possible characters
    for (var ch = 0; ch < 26; ch++) {
        var c = String.fromCharCode('a'.charCodeAt(0) + ch);
 
        // stores the last occurrence
        var last = -1;
 
        // set answer as true;
        var found = true;
        for (var i = 0; i < K; i++)
            if (s[i] == c)
                last = i;
 
        // No occurrence found of current
        // character in first substring
        // of length K
        if (last == -1)
            continue;
 
        // Check for every last substring
        // of length K where last occurr-
        // ence exists in substring
        for (var i = K; i < s.length; i++) {
            if (s[i] == c)
                last = i;
 
            // If last occ is not
            // present in substring
            if (last <= (i - K)) {
                found = false;
                break;
            }
        }
        // current character is K amazing
        if (found)
            return 1;
    }
    return 0;
}
 
// This function performs binary search over the
// answer to minimise it
function binarySearch(s)
{
    var low = 1, high = s.length;
    var ans;
    while (low <= high) {
        var mid = (high + low) >> 1;
 
        // Check if answer is found try
        // to minimise it
        if (check(s, mid)) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    return ans;
}
 
// Driver Code to test above functions
var s = "abcde";
document.write( binarySearch(s) + "<br>");
s = "aaaa";
document.write( binarySearch(s) );
 
</script>
Producción: 

3
1

 

Complejidad de tiempo: O (N * logN * 26), donde N es el tamaño de la string dada.
 

Publicación traducida automáticamente

Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *