Dada la string str , un carácter c y un entero k > 0 . La tarea es encontrar el número de substrings que contienen el carácter c exactamente k veces.
Ejemplos:
Entrada: str = “abada”, c = ‘a’, K = 2
Salida: 4
Todas las substrings posibles son “aba”, “abad”, “bada” y “ada”.Entrada: str = “55555”, c = ‘5’, k = 4
Salida: 2
Enfoque ingenuo: una solución simple es generar todas las substrings y verificar si el conteo de un carácter dado es exactamente k veces.
La complejidad temporal de este enfoque es O(n 2 ) .
Enfoque eficiente: una solución eficiente es utilizar la técnica de la ventana deslizante. Encuentre la substring que contiene exactamente el carácter dado k veces, comenzando con el carácter c. Cuente el número de caracteres a cada lado de la substring. Multiplique los recuentos para obtener el número de posibles substrings. La complejidad temporal de este enfoque es O(n) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of required sub-strings
int countSubString(string s, char c, int k)
{
// Left and right counters for characters on
// both sides of sub-string window
int leftCount = 0, rightCount = 0;
// Left and right pointer on both
// sides of sub-string window
int left = 0, right = 0;
// Initialize the frequency
int freq = 0;
// Result and length of string
int result = 0, len = s.length();
// Initialize the left pointer
while (s[left] != c && left < len) {
left++;
leftCount++;
}
// Initialize the right pointer
right = left + 1;
while (freq != (k - 1) && (right - 1) < len) {
if (s[right] == c)
freq++;
right++;
}
// Traverse all the window sub-strings
while (left < len && (right - 1) < len) {
// Counting the characters on left side
// of the sub-string window
while (s[left] != c && left < len) {
left++;
leftCount++;
}
// Counting the characters on right side
// of the sub-string window
while (right < len && s[right] != c) {
if (s[right] == c)
freq++;
right++;
rightCount++;
}
// Add the possible sub-strings
// on both sides to result
result = result + (leftCount + 1) * (rightCount + 1);
// Setting the frequency for next
// sub-string window
freq = k - 1;
// Reset the left and right counters
leftCount = 0;
rightCount = 0;
left++;
right++;
}
return result;
}
// Driver code
int main()
{
string s = "abada";
char c = 'a';
int k = 2;
cout << countSubString(s, c, k) << "\n";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the count of required sub-strings
static int countSubString(char[] s, char c, int k)
{
// Left and right counters for characters on
// both sides of sub-string window
int leftCount = 0, rightCount = 0;
// Left and right pointer on both
// sides of sub-string window
int left = 0, right = 0;
// Initialize the frequency
int freq = 0;
// Result and length of string
int result = 0, len = s.length;
// Initialize the left pointer
while (s[left] != c && left < len)
{
left++;
leftCount++;
}
// Initialize the right pointer
right = left + 1;
while (freq != (k - 1) && (right - 1) < len)
{
if (s[right] == c)
freq++;
right++;
}
// Traverse all the window sub-strings
while (left < len && (right - 1) < len)
{
// Counting the characters on left side
// of the sub-string window
while (s[left] != c && left < len)
{
left++;
leftCount++;
}
// Counting the characters on right side
// of the sub-string window
while (right < len && s[right] != c)
{
if (s[right] == c)
freq++;
right++;
rightCount++;
}
// Add the possible sub-strings
// on both sides to result
result = result + (leftCount + 1) * (rightCount + 1);
// Setting the frequency for next
// sub-string window
freq = k - 1;
// Reset the left and right counters
leftCount = 0;
rightCount = 0;
left++;
right++;
}
return result;
}
// Driver code
public static void main(String[] args)
{
String s = "abada";
char c = 'a';
int k = 2;
System.out.println(countSubString(s.toCharArray(), c, k));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach # Function to return the count # of required sub-strings def countSubString(s, c, k): # Left and right counters for characters # on both sides of sub-string window leftCount = 0 rightCount = 0 # Left and right pointer on both # sides of sub-string window left = 0 right = 0 # Initialize the frequency freq = 0 # Result and length of string result = 0 len1 = len(s) # Initialize the left pointer while (s[left] != c and left < len1): left += 1 leftCount += 1 # Initialize the right pointer right = left + 1 while (freq != (k - 1) and (right - 1) < len1): if (s[right] == c): freq += 1 right += 1 # Traverse all the window sub-strings while (left < len1 and (right - 1) < len1): # Counting the characters on left side # of the sub-string window while (s[left] != c and left < len1): left += 1 leftCount += 1 # Counting the characters on right side # of the sub-string window while (right < len1 and s[right] != c): if (s[right] == c): freq += 1 right += 1 rightCount += 1 # Add the possible sub-strings # on both sides to result result = (result + (leftCount + 1) * (rightCount + 1)) # Setting the frequency for next # sub-string window freq = k - 1 # Reset the left and right counters leftCount = 0 rightCount = 0 left += 1 right += 1 return result # Driver code if __name__ == '__main__': s = "abada" c = 'a' k = 2 print(countSubString(s, c, k)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of required sub-strings
static int countSubString(char[] s, char c, int k)
{
// Left and right counters for characters on
// both sides of sub-string window
int leftCount = 0, rightCount = 0;
// Left and right pointer on both
// sides of sub-string window
int left = 0, right = 0;
// Initialize the frequency
int freq = 0;
// Result and length of string
int result = 0, len = s.Length;
// Initialize the left pointer
while (s[left] != c && left < len)
{
left++;
leftCount++;
}
// Initialize the right pointer
right = left + 1;
while (freq != (k - 1) && (right - 1) < len)
{
if (s[right] == c)
freq++;
right++;
}
// Traverse all the window sub-strings
while (left < len && (right - 1) < len)
{
// Counting the characters on left side
// of the sub-string window
while (s[left] != c && left < len)
{
left++;
leftCount++;
}
// Counting the characters on right side
// of the sub-string window
while (right < len && s[right] != c)
{
if (s[right] == c)
freq++;
right++;
rightCount++;
}
// Add the possible sub-strings
// on both sides to result
result = result + (leftCount + 1) * (rightCount + 1);
// Setting the frequency for next
// sub-string window
freq = k - 1;
// Reset the left and right counters
leftCount = 0;
rightCount = 0;
left++;
right++;
}
return result;
}
// Driver code
public static void Main(String[] args)
{
String s = "abada";
char c = 'a';
int k = 2;
Console.WriteLine(countSubString(s.ToCharArray(), c, k));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the approach
// Function to return the count of required sub-strings
function countSubString($s, $c, $k)
{
// Left and right counters for characters on
// both sides of sub-string window
$leftCount = 0; $rightCount = 0;
// Left and right pointer on both
// sides of sub-string window
$left = 0; $right = 0;
// Initialize the frequency
$freq = 0;
// Result and length of string
$result = 0; $len = strlen($s);
// Initialize the left pointer
while ($s[$left] != $c && $left < $len)
{
$left++;
$leftCount++;
}
// Initialize the right pointer
$right = $left + 1;
while ($freq != ($k - 1) && ($right - 1) < $len)
{
if ($s[$right] == $c)
$freq++;
$right++;
}
// Traverse all the window sub-strings
while ($left < $len && ($right - 1) < $len)
{
// Counting the characters on left side
// of the sub-string window
while ($s[$left] != $c && $left < $len)
{
$left++;
$leftCount++;
}
// Counting the characters on right side
// of the sub-string window
while ($right < $len && $s[$right] != $c)
{
if ($s[$right] == $c)
$freq++;
$right++;
$rightCount++;
}
// Add the possible sub-strings
// on both sides to result
$result = $result + ($leftCount + 1) *
($rightCount + 1);
// Setting the frequency for next
// sub-string window
$freq = $k - 1;
// Reset the left and right counters
$leftCount = 0;
$rightCount = 0;
$left++;
$right++;
}
return $result;
}
// Driver code
$s = "abada";
$c = 'a';
$k = 2;
echo countSubString($s, $c, $k), "\n";
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of required sub-strings
function countSubString(s, c, k)
{
// Left and right counters for characters on
// both sides of sub-string window
var leftCount = 0, rightCount = 0;
// Left and right pointer on both
// sides of sub-string window
var left = 0, right = 0;
// Initialize the frequency
var freq = 0;
// Result and length of string
var result = 0, len = s.length;
// Initialize the left pointer
while (s[left] != c && left < len) {
left++;
leftCount++;
}
// Initialize the right pointer
right = left + 1;
while (freq != (k - 1) && (right - 1) < len) {
if (s[right] == c)
freq++;
right++;
}
// Traverse all the window sub-strings
while (left < len && (right - 1) < len) {
// Counting the characters on left side
// of the sub-string window
while (s[left] != c && left < len) {
left++;
leftCount++;
}
// Counting the characters on right side
// of the sub-string window
while (right < len && s[right] != c) {
if (s[right] == c)
freq++;
right++;
rightCount++;
}
// Add the possible sub-strings
// on both sides to result
result = result + (leftCount + 1) * (rightCount + 1);
// Setting the frequency for next
// sub-string window
freq = k - 1;
// Reset the left and right counters
leftCount = 0;
rightCount = 0;
left++;
right++;
}
return result;
}
// Driver code
var s = "abada";
var c = 'a';
var k = 2;
document.write( countSubString(s, c, k) + "<br>");
</script>
Producción:
4
Publicación traducida automáticamente
Artículo escrito por Sairahul Jella y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA