Dadas dos strings S y T de longitud N y M respectivamente, la tarea es contar el número de formas de obtener una substring de la misma longitud de ambas strings de manera que tengan un solo carácter diferente.
Ejemplos:
Entrada: S = «ab», T = «bb»
Salida: 3
Explicación: Los siguientes son los pares de substrings de S y T que difieren en un solo carácter:
- (“a”, “b”)
- (“a”, “b”)
- (“ab”, “bb”)
Entrada: S = “aba”, T = “baba”
Salida: 6
Enfoque ingenuo: el enfoque más simple es generar todas las substrings posibles a partir de las dos strings dadas y luego contar todos los pares posibles de substrings de la misma longitud que se pueden igualar cambiando un solo carácter.
Complejidad de Tiempo: O(N 3 *M 3 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: para optimizar el enfoque anterior, la idea es iterar sobre todos los caracteres de las strings dadas simultáneamente y para cada par de caracteres diferentes, contar todas esas substrings de igual longitud a partir del siguiente índice del carácter diferente actual. Imprime el conteo obtenido después de verificar todos los pares de caracteres diferentes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// substrings of equal length which
// differ by a single character
int countSubstrings(string s, string t)
{
// Stores the count of
// pairs of substrings
int answ = 0;
// Traverse the string s
for(int i = 0; i < s.size(); i++)
{
// Traverse the string t
for(int j = 0; j < t.size(); j++)
{
// Different character
if (t[j] != s[i])
{
// Increment the answer
answ += 1;
int k = 1;
int z = -1;
int q = 1;
// Count equal substrings
// from next index
while (j + z >= 0 &&
0 <= i + z &&
s[i + z] ==
t[j + z])
{
z -= 1;
// Increment the count
answ += 1;
// Increment q
q += 1;
}
// Check the condition
while (s.size() > i + k &&
j + k < t.size() &&
s[i + k] ==
t[j + k])
{
// Increment k
k += 1;
// Add q to count
answ += q;
// Decrement z
z = -1;
}
}
}
}
// Return the final count
return answ;
}
// Driver Code
int main()
{
string S = "aba";
string T = "baba";
// Function Call
cout<<(countSubstrings(S, T));
}
// This code is contributed by 29AjayKumar
Java
// Java program for the above approach
class GFG{
// Function to count the number of
// subStrings of equal length which
// differ by a single character
static int countSubStrings(String s, String t)
{
// Stores the count of
// pairs of subStrings
int answ = 0;
// Traverse the String s
for(int i = 0; i < s.length(); i++)
{
// Traverse the String t
for(int j = 0; j < t.length(); j++)
{
// Different character
if (t.charAt(j) != s.charAt(i))
{
// Increment the answer
answ += 1;
int k = 1;
int z = -1;
int q = 1;
// Count equal subStrings
// from next index
while (j + z >= 0 &&
0 <= i + z &&
s.charAt(i + z) ==
t.charAt(j + z))
{
z -= 1;
// Increment the count
answ += 1;
// Increment q
q += 1;
}
// Check the condition
while (s.length() > i + k &&
j + k < t.length() &&
s.charAt(i + k) ==
t.charAt(j + k))
{
// Increment k
k += 1;
// Add q to count
answ += q;
// Decrement z
z = -1;
}
}
}
}
// Return the final count
return answ;
}
// Driver Code
public static void main(String[] args)
{
String S = "aba";
String T = "baba";
// Function Call
System.out.println(countSubStrings(S, T));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function to count the number of # substrings of equal length which # differ by a single character def countSubstrings(s, t): # Stores the count of # pairs of substrings answ = 0 # Traverse the string s for i in range(len(s)): # Traverse the string t for j in range(len(t)): # Different character if t[j] != s[i]: # Increment the answer answ += 1 k = 1 z = -1 q = 1 # Count equal substrings # from next index while ( j + z >= 0 <= i + z and s[i + z] == t[j + z] ): z -= 1 # Increment the count answ += 1 # Increment q q += 1 # Check the condition while ( len(s) > i + k and j + k < len(t) and s[i + k] == t[j + k] ): # Increment k k += 1 # Add q to count answ += q # Decrement z z = -1 # Return the final count return answ # Driver Code S = "aba" T = "baba" # Function Call print(countSubstrings(S, T))
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count the number of
// subStrings of equal length which
// differ by a single character
static int countSubStrings(String s, String t)
{
// Stores the count of
// pairs of subStrings
int answ = 0;
// Traverse the String s
for(int i = 0; i < s.Length; i++)
{
// Traverse the String t
for(int j = 0; j < t.Length; j++)
{
// Different character
if (t[j] != s[i])
{
// Increment the answer
answ += 1;
int k = 1;
int z = -1;
int q = 1;
// Count equal subStrings
// from next index
while (j + z >= 0 &&
0 <= i + z &&
s[i + z] ==
t[j + z])
{
z -= 1;
// Increment the count
answ += 1;
// Increment q
q += 1;
}
// Check the condition
while (s.Length > i + k &&
j + k < t.Length &&
s[i + k] ==
t[j + k])
{
// Increment k
k += 1;
// Add q to count
answ += q;
// Decrement z
z = -1;
}
}
}
}
// Return the readonly count
return answ;
}
// Driver Code
public static void Main(String[] args)
{
String S = "aba";
String T = "baba";
// Function Call
Console.WriteLine(countSubStrings(S, T));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count the number of
// subStrings of equal length which
// differ by a single character
function countSubStrings(s, t)
{
// Stores the count of
// pairs of subStrings
let answ = 0;
// Traverse the String s
for(let i = 0; i < s.length; i++)
{
// Traverse the String t
for(let j = 0; j < t.length; j++)
{
// Different character
if (t[j] != s[i])
{
// Increment the answer
answ += 1;
let k = 1;
let z = -1;
let q = 1;
// Count equal subStrings
// from next index
while (j + z >= 0 &&
0 <= i + z &&
s[i + z] ==
t[j + z])
{
z -= 1;
// Increment the count
answ += 1;
// Increment q
q += 1;
}
// Check the condition
while (s.length > i + k &&
j + k < t.length &&
s[i + k] ==
t[j + k])
{
// Increment k
k += 1;
// Add q to count
answ += q;
// Decrement z
z = -1;
}
}
}
}
// Return the readonly count
return answ;
}
// Driver Code
let S = "aba";
let T = "baba";
// Function Call
document.write(countSubStrings(S, T));
// This code is contributed by souravghosh0416.
</script>
6
Complejidad de tiempo: O(N*M*max(N,M))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA