Dada una string str que consiste en letras en minúsculas, la tarea es encontrar el número de posibles substrings (no necesariamente distintas) que consisten solo en caracteres distintos.
Ejemplos:
Entrada: Str = «gffg»
Salida: 6
Explicación:
Todas las substrings posibles de la string dada son,
( » g «, » gf «, «gff», «gffg», » f «, «ff», «ffg», “ f ”, “ fg ”, “ g ”)
Entre ellos, los resaltados consisten solo en caracteres distintos.Entrada: str = “gfg”
Salida: 5
Explicación:
Todas las substrings posibles de la string dada son,
( “ g “, “ gf “, “gfg”, “ f “, “ fg “, “ g ”)
Entre ellas, la resaltado consta únicamente de caracteres distintos.
Enfoque ingenuo:
el enfoque más simple es generar todas las substrings posibles a partir de la string dada y verificar si cada substring contiene todos los caracteres distintos o no. Si la longitud de la string es N , habrá N*(N+1)/2 posibles substrings.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(1)
Enfoque eficiente:
el problema se puede resolver en tiempo lineal utilizando la técnica de dos punteros , con la ayuda de contar las frecuencias de los caracteres de la string.
Los pasos detallados para este enfoque son los siguientes:
- Considere dos punteros i y j , inicialmente ambos apuntando al primer carácter de la string , es decir i = j = 0 .
- Inicialice una array Cnt[ ] para almacenar el recuento de caracteres en la substring desde el índice i al j , ambos inclusive.
- Ahora, siga incrementando el puntero j hasta que se encuentre algún carácter repetido. Mientras incrementa j , agregue el conteo de todas las substrings que terminan en el j -ésimo índice y comienzan en cualquier índice entre i y j a la respuesta. Todas estas substrings contendrán caracteres distintos ya que no se repite ningún carácter en ellas.
- Si se encuentra algún carácter repetido en la substring entre el índice i al j , para excluir este carácter repetido, siga incrementando el puntero i hasta que se elimine el carácter repetido y siga actualizando la array Cnt[ ] en consecuencia.
- Continúe este proceso hasta que j llegue al final de la string. Una vez que la string se atraviese por completo, imprima la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count total
// number of valid substrings
long long int countSub(string str)
{
int n = (int)str.size();
// Stores the count of
// substrings
long long int ans = 0;
// Stores the frequency
// of characters
int cnt[26];
memset(cnt, 0, sizeof(cnt));
// Initialised both pointers
// to beginning of the string
int i = 0, j = 0;
while (i < n) {
// If all characters in
// substring from index i
// to j are distinct
if (j < n && (cnt[str[j] - 'a']
== 0)) {
// Increment count of j-th
// character
cnt[str[j] - 'a']++;
// Add all substring ending
// at j and starting at any
// index between i and j
// to the answer
ans += (j - i + 1);
// Increment 2nd pointer
j++;
}
// If some characters are repeated
// or j pointer has reached to end
else {
// Decrement count of j-th
// character
cnt[str[i] - 'a']--;
// Increment first pointer
i++;
}
}
// Return the final
// count of substrings
return ans;
}
// Driver Code
int main()
{
string str = "gffg";
cout << countSub(str);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to count total
// number of valid subStrings
static int countSub(String str)
{
int n = (int)str.length();
// Stores the count of
// subStrings
int ans = 0;
// Stores the frequency
// of characters
int []cnt = new int[26];
// Initialised both pointers
// to beginning of the String
int i = 0, j = 0;
while (i < n)
{
// If all characters in
// subString from index i
// to j are distinct
if (j < n &&
(cnt[str.charAt(j) - 'a'] == 0))
{
// Increment count of j-th
// character
cnt[str.charAt(j) - 'a']++;
// Add all subString ending
// at j and starting at any
// index between i and j
// to the answer
ans += (j - i + 1);
// Increment 2nd pointer
j++;
}
// If some characters are repeated
// or j pointer has reached to end
else
{
// Decrement count of j-th
// character
cnt[str.charAt(i) - 'a']--;
// Increment first pointer
i++;
}
}
// Return the final
// count of subStrings
return ans;
}
// Driver Code
public static void main(String[] args)
{
String str = "gffg";
System.out.print(countSub(str));
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program to implement
# the above approach
# Function to count total
# number of valid substrings
def countSub(Str):
n = len(Str)
# Stores the count of
# substrings
ans = 0
# Stores the frequency
# of characters
cnt = 26 * [0]
# Initialised both pointers
# to beginning of the string
i, j = 0, 0
while (i < n):
# If all characters in
# substring from index i
# to j are distinct
if (j < n and
(cnt[ord(Str[j]) - ord('a')] == 0)):
# Increment count of j-th
# character
cnt[ord(Str[j]) - ord('a')] += 1
# Add all substring ending
# at j and starting at any
# index between i and j
# to the answer
ans += (j - i + 1)
# Increment 2nd pointer
j += 1
# If some characters are repeated
# or j pointer has reached to end
else:
# Decrement count of j-th
# character
cnt[ord(Str[i]) - ord('a')] -= 1
# Increment first pointer
i += 1
# Return the final
# count of substrings
return ans
# Driver code
Str = "gffg"
print(countSub(Str))
# This code is contributed by divyeshrabadiya07
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to count total
// number of valid subStrings
static int countSub(String str)
{
int n = (int)str.Length;
// Stores the count of
// subStrings
int ans = 0;
// Stores the frequency
// of characters
int []cnt = new int[26];
// Initialised both pointers
// to beginning of the String
int i = 0, j = 0;
while (i < n)
{
// If all characters in
// subString from index i
// to j are distinct
if (j < n &&
(cnt[str[j] - 'a'] == 0))
{
// Increment count of j-th
// character
cnt[str[j] - 'a']++;
// Add all subString ending
// at j and starting at any
// index between i and j
// to the answer
ans += (j - i + 1);
// Increment 2nd pointer
j++;
}
// If some characters are repeated
// or j pointer has reached to end
else
{
// Decrement count of j-th
// character
cnt[str[i] - 'a']--;
// Increment first pointer
i++;
}
}
// Return the final
// count of subStrings
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String str = "gffg";
Console.Write(countSub(str));
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to count total
// number of valid substrings
function countSub(str)
{
var n = str.length;
// Stores the count of
// substrings
var ans = 0;
// Stores the frequency
// of characters
var cnt = Array(26).fill(0);
// Initialised both pointers
// to beginning of the string
var i = 0, j = 0;
while (i < n) {
// If all characters in
// substring from index i
// to j are distinct
if (j < n && (cnt[str[j].charCodeAt(0) - 'a'.charCodeAt(0)]
== 0)) {
// Increment count of j-th
// character
cnt[str[j].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// Add all substring ending
// at j and starting at any
// index between i and j
// to the answer
ans += (j - i + 1);
// Increment 2nd pointer
j++;
}
// If some characters are repeated
// or j pointer has reached to end
else {
// Decrement count of j-th
// character
cnt[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]--;
// Increment first pointer
i++;
}
}
// Return the final
// count of substrings
return ans;
}
// Driver Code
var str = "gffg";
document.write( countSub(str));
</script>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)