Dada una string. La tarea es averiguar el número de substrings que constan de los mismos caracteres.
Ejemplos:
Entrada: abba
Salida: 5
Las substrings deseadas son {a}, {b}, {b}, {a}, {bb}Entrada: bbbcbb
Salida: 10
Enfoque: Se sabe que para una string de longitud n , hay un total de n*(n+1)/2 número de substrings.
Inicialicemos el resultado a 0. Recorra la string y encuentre el número de elementos consecutivos (digamos contar ) de los mismos caracteres. Cada vez que encontremos otro carácter, incrementamos el resultado en count*(count+1)/2 , establecemos count en 1 y, a partir de ese índice, repetimos el proceso anterior.
Recuerde, para cada carácter diferente, el número de nuestra substring deseada es 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation
// of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// number of substrings of
// same characters
void findNumbers(string s)
{
if (s.empty()) return 0;
// Size of the string
int n = s.size();
// Initialize count to 1
int count = 1;
int result = 0;
// Initialize left to 0 and
// right to 1 to traverse the
// string
int left = 0;
int right = 1;
while (right < n) {
// Checking if consecutive
// characters are same and
// increment the count
if (s[left] == s[right]) {
count++;
}
// When we encounter a
// different characters
else {
// Increment the result
result += count * (count + 1) / 2;
// To repeat the whole
// process set left equals
// right and count variable to 1
left = right;
count = 1;
}
right++;
}
// Store the final
// value of result
result += count * (count + 1) / 2;
cout << result << endl;
}
// Driver code
int main()
{
string s = "bbbcbb";
findNumbers(s);
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the
// number of substrings of
// same characters
static void findNumbers(String s)
{
// Size of the string
int n = s.length();
// Initialize count to 1
int count = 1;
int result = 0;
// Initialize left to 0 and
// right to 1 to traverse the
// string
int left = 0;
int right = 1;
while (right < n)
{
// Checking if consecutive
// characters are same and
// increment the count
if (s.charAt(left) == s.charAt(right))
{
count++;
}
// When we encounter a
// different characters
else
{
// Increment the result
result += count * (count + 1) / 2;
// To repeat the whole
// process set left equals
// right and count variable to 1
left = right;
count = 1;
}
right++;
}
// Store the final
// value of result
result += count * (count + 1) / 2;
System.out.println(result);
}
// Driver code
public static void main (String[] args)
{
String s = "bbbcbb";
findNumbers(s);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the above approach # Function to return the number of # substrings of same characters def findNumbers(s): # Size of the string n = len(s) # Initialize count to 1 count = 1 result = 0 # Initialize left to 0 and right to 1 # to traverse the string left = 0 right = 1 while (right < n): # Checking if consecutive # characters are same and # increment the count if (s[left] == s[right]): count += 1 # When we encounter a # different characters else: # Increment the result result += count * (count + 1) // 2 # To repeat the whole # process set left equals # right and count variable to 1 left = right count = 1 right += 1 # Store the final value of result result += count * (count + 1) // 2 print(result) # Driver code s = "bbbcbb" findNumbers(s) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the
// number of substrings of
// same characters
static void findNumbers(String s)
{
// Size of the string
int n = s.Length;
// Initialize count to 1
int count = 1;
int result = 0;
// Initialize left to 0 and
// right to 1 to traverse the
// string
int left = 0;
int right = 1;
while (right < n)
{
// Checking if consecutive
// characters are same and
// increment the count
if (s[left] == s[right])
count++;
// When we encounter a
// different characters
else
{
// Increment the result
result += count * (count + 1) / 2;
// To repeat the whole
// process set left equals
// right and count variable to 1
left = right;
count = 1;
}
right++;
}
// Store the final
// value of result
result += count * (count + 1) / 2;
Console.WriteLine(result);
}
// Driver code
public static void Main(String[] args)
{
String s = "bbbcbb";
findNumbers(s);
}
}
// This code is contributed by
// sanjeev2552
Javascript
<script>
// Javascript implementation
// of the above approach
// Function to return the
// number of substrings of
// same characters
function findNumbers(s)
{
// Size of the string
var n = s.length;
// Initialize count to 1
var count = 1;
var result = 0;
// Initialize left to 0 and
// right to 1 to traverse the
// string
var left = 0;
var right = 1;
while (right < n)
{
// Checking if consecutive
// characters are same and
// increment the count
if (s[left] == s[right])
{
count++;
}
// When we encounter a
// different characters
else
{
// Increment the result
result += parseInt(count * (count + 1) / 2);
// To repeat the whole
// process set left equals
// right and count variable to 1
left = right;
count = 1;
}
right++;
}
// Store the final
// value of result
result += parseInt(count * (count + 1) / 2);
document.write(result);
}
// Driver code
var s = "bbbcbb";
findNumbers(s);
// This code is contributed by itsok
</script>
Producción:
10
Publicación traducida automáticamente
Artículo escrito por dangenmaster2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA