Dada una string str que consta solo de alfabetos ingleses en minúsculas, la tarea es contar el número de formas de eliminar exactamente una substring de str de modo que todos los caracteres restantes sean iguales.
Nota: Hay al menos dos caracteres diferentes en str y también podemos eliminar toda la string.
Ejemplos:
Entrada: str = “abaa”
Salida: 6
Podemos eliminar las siguientes substrings para satisfacer la condición dada:
str[0:1], str[0:2], str[0:3], str[1:1 ], str[1:2] y str[1:3]
Entrada: str = “geeksforgeeks”
Salida: 3 Eliminamos
string completa.
Quitamos todos menos el primero.
Quitamos todos menos el último
Acercarse:
- Almacene la longitud del prefijo y el sufijo de los mismos caracteres de la string en las variables count_left y count_right .
- Es obvio que este prefijo y sufijo no se superpondrán, ya que hay al menos dos caracteres diferentes en str .
- Ahora hay 2 casos:
- Cuando str[0] = str[n – 1] , cada carácter del prefijo (incluido el carácter justo después de que finalice el prefijo) actuará como el carácter inicial de la substring y cada carácter del sufijo (incluido el carácter justo antes de que comience el sufijo) actuará como el carácter final de la substring. Por lo tanto, el total de substrings válidas será count = (count_left + 1) * (count_right + 1) .
- Cuando string[0] != string[n – 1] . luego contar = contar_izquierda + contar_derecha + 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count number of ways of
// removing a substring from a string such
// that all remaining characters are equal
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of ways
// of removing a sub-string from s such
// that all the remaining characters are same
int no_of_ways(string s)
{
int n = s.length();
// To store the count of prefix and suffix
int count_left = 0, count_right = 0;
// Loop to count prefix
for (int i = 0; i < n; ++i) {
if (s[i] == s[0]) {
++count_left;
}
else
break;
}
// Loop to count suffix
for (int i = n - 1; i >= 0; --i) {
if (s[i] == s[n - 1]) {
++count_right;
}
else
break;
}
// First and last characters of the
// string are same
if (s[0] == s[n - 1])
return ((count_left + 1) * (count_right + 1));
// Otherwise
else
return (count_left + count_right + 1);
}
// Driver function
int main()
{
string s = "geeksforgeeks";
cout << no_of_ways(s);
return 0;
}
Java
// Java program to count number of ways of
// removing a substring from a string such
// that all remaining characters are equal
import java.util.*;
class solution
{
// Function to return the number of ways
// of removing a sub-string from s such
// that all the remaining characters are same
static int no_of_ways(String s)
{
int n = s.length();
// To store the count of prefix and suffix
int count_left = 0, count_right = 0;
// Loop to count prefix
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == s.charAt(0)) {
++count_left;
}
else
break;
}
// Loop to count suffix
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == s.charAt(n - 1)) {
++count_right;
}
else
break;
}
// First and last characters of the
// string are same
if (s.charAt(0) == s.charAt(n - 1))
return ((count_left + 1) * (count_right + 1));
// Otherwise
else
return (count_left + count_right + 1);
}
// Driver function
public static void main(String args[])
{
String s = "geeksforgeeks";
System.out.println(no_of_ways(s));
}
}
Python3
# Python 3 program to count number of # ways of removing a substring from a # string such that all remaining # characters are equal # Function to return the number of # ways of removing a sub-string from # s such that all the remaining # characters are same def no_of_ways(s): n = len(s) # To store the count of # prefix and suffix count_left = 0 count_right = 0 # Loop to count prefix for i in range(0, n, 1): if (s[i] == s[0]): count_left += 1 else: break # Loop to count suffix i = n - 1 while(i >= 0): if (s[i] == s[n - 1]): count_right += 1 else: break i -= 1 # First and last characters of # the string are same if (s[0] == s[n - 1]): return ((count_left + 1) * (count_right + 1)) # Otherwise else: return (count_left + count_right + 1) # Driver Code if __name__ == '__main__': s = "geeksforgeeks" print(no_of_ways(s)) # This code is contributed by # Sahil_shelengia
C#
// C# program to count number of ways of
// removing a substring from a string such
// that all remaining characters are equal
using System;
class GFG
{
// Function to return the number of ways
// of removing a sub-string from s such
// that all the remaining characters are same
static int no_of_ways(string s)
{
int n = s.Length;
// To store the count of prefix and suffix
int count_left = 0, count_right = 0;
// Loop to count prefix
for (int i = 0; i < n; ++i)
{
if (s[i] == s[0])
{
++count_left;
}
else
break;
}
// Loop to count suffix
for (int i = n - 1; i >= 0; --i)
{
if (s[i] == s[n - 1])
{
++count_right;
}
else
break;
}
// First and last characters of the
// string are same
if (s[0] == s[n - 1])
return ((count_left + 1) *
(count_right + 1));
// Otherwise
else
return (count_left + count_right + 1);
}
// Driver Code
public static void Main()
{
string s = "geeksforgeeks";
Console.WriteLine(no_of_ways(s));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program to count number of ways of
// removing a substring from a string such
// that all remaining characters are equal
// Function to return the number of ways
// of removing a sub-string from $s such
// that all the remaining characters are same
function no_of_ways($s)
{
$n = strlen($s);
// To store the count of prefix and suffix
$count_left = 0;
$count_right = 0;
// Loop to count prefix
for ($i = 0; $i < $n; ++$i)
{
if ($s[$i] == $s[0])
{
++$count_left;
}
else
break;
}
// Loop to count suffix
for ($i = $n - 1; $i >= 0; --$i)
{
if ($s[$i] == $s[$n - 1])
{
++$count_right;
}
else
break;
}
// First and last characters of the
// string are same
if ($s[0] == $s[$n - 1])
return (($count_left + 1) *
($count_right + 1));
// Otherwise
else
return ($count_left + $count_right + 1);
}
// Driver Code
$s = "geeksforgeeks";
echo no_of_ways($s);
// This code is contributed by ihritik
?>
Javascript
<script>
// JavaScript program to count number of ways of
// removing a substring from a string such
// that all remaining characters are equal
// Function to return the number of ways
// of removing a sub-string from s such
// that all the remaining characters are same
function no_of_ways(s)
{
let n = s.length;
// To store the count of prefix and suffix
let count_left = 0, count_right = 0;
// Loop to count prefix
for (let i = 0; i < n; ++i)
{
if (s[i] == s[0])
{
++count_left;
}
else
break;
}
// Loop to count suffix
for (let i = n - 1; i >= 0; --i)
{
if (s[i] == s[n - 1])
{
++count_right;
}
else
break;
}
// First and last characters of the
// string are same
if (s[0] == s[n - 1])
return ((count_left + 1) *
(count_right + 1));
// Otherwise
else
return (count_left + count_right + 1);
}
let s = "geeksforgeeks";
document.write(no_of_ways(s));
</script>
Producción:
3
Complejidad de tiempo: O(n), donde n es el tamaño de la string dada
Espacio auxiliar: O(1), ya que no se requiere espacio adicional