Nos dan una string S, necesitamos encontrar el recuento de todas las substrings contiguas que comienzan y terminan con el mismo carácter.
Ejemplos:
Input : S = "abcab" Output : 7 There are 15 substrings of "abcab" a, ab, abc, abca, abcab, b, bc, bca bcab, c, ca, cab, a, ab, b Out of the above substrings, there are 7 substrings : a, abca, b, bcab, c, a and b. Input : S = "aba" Output : 4 The substrings are a, b, a and aba
Método 1 (Simple): en este enfoque, usamos la fuerza bruta y buscamos todas las substrings y las pasamos a través de nuestra función checkEquality para ver si los caracteres iniciales y finales son los mismos.
Implementación:
C++
// C++ program to count all substrings with same
// first and last characters.
#include <bits/stdc++.h>
using namespace std;
// Returns true if first and last characters
// of s are same.
int checkEquality(string s)
{
return (s[0] == s[s.size() - 1]);
}
int countSubstringWithEqualEnds(string s)
{
int result = 0;
int n = s.length();
// Starting point of substring
for (int i = 0; i < n; i++)
// Length of substring
for (int len = 1; len <= n-i; len++)
// Check if current substring has same
// starting and ending characters.
if (checkEquality(s.substr(i, len)))
result++;
return result;
}
// Driver function
int main()
{
string s("abcab");
cout << countSubstringWithEqualEnds(s);
return 0;
}
Java
// Java program to count all substrings with same
// first and last characters.
public class GFG {
// Returns true if first and last characters
// of s are same.
static boolean checkEquality(String s)
{
return (s.charAt(0) == s.charAt(s.length() - 1));
}
static int countSubstringWithEqualEnds(String s)
{
int result = 0;
int n = s.length();
// Starting point of substring
for (int i = 0; i < n; i++)
// Length of substring
for (int len = 1; len <= n-i; len++)
// Check if current substring has same
// starting and ending characters.
if (checkEquality(s.substring(i, i + len)))
result++;
return result;
}
// Driver function
public static void main(String args[])
{
String s = "abcab";
System.out.println(countSubstringWithEqualEnds(s));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program to count all substrings with same # first and last characters. # Returns true if first and last characters # of s are same. def checkEquality(s): return (ord(s[0]) == ord(s[len(s) - 1])); def countSubstringWithEqualEnds(s): result = 0; n = len(s); # Starting point of substring for i in range(n): # Length of substring for j in range(1,n-i+1): # Check if current substring has same # starting and ending characters. if (checkEquality(s[i:i+j])): result+=1; return result; # Driver code s = "abcab"; print(countSubstringWithEqualEnds(s)); # This code contributed by PrinciRaj1992
C#
// C# program to count all
// substrings with same
// first and last characters.
using System;
class GFG
{
// Returns true if first and
// last characters of s are same.
static bool checkEquality(string s)
{
return (s[0] == s[s.Length - 1]);
}
static int countSubstringWithEqualEnds(string s)
{
int result = 0;
int n = s.Length;
// Starting point of substring
for (int i = 0; i < n; i++)
// Length of substring
for (int len = 1; len <= n-i; len++)
// Check if current substring has same
// starting and ending characters.
if (checkEquality(s.Substring(i, len)))
result++;
return result;
}
// Driver code
public static void Main()
{
string s = "abcab";
Console.WriteLine(countSubstringWithEqualEnds(s));
}
}
// This code is contributed by Code_Mech
PHP
<?php
// PHP program to count all substrings
// with same first and last characters.
// Returns true if first and last
// characters of s are same.
function checkEquality($s)
{
return ($s[0] == $s[strlen($s) - 1]);
}
function countSubstringWithEqualEnds($s)
{
$result = 0;
$n = strlen($s);
// Starting point of substring
for ($i = 0; $i < $n; $i++)
// Length of substring
for ($len = 1; $len <= $n - $i; $len++)
// Check if current substring has same
// starting and ending characters.
if (checkEquality(substr($s, $i, $len)))
$result++;
return $result;
}
// Driver Code
$s = "abcab";
print(countSubstringWithEqualEnds($s));
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// JavaScript program to count all substrings
// with same first and last characters.
// Returns true if first and last characters
// of s are same.
function checkEquality(s)
{
return (s.charAt(0) == s.charAt(s.length - 1));
}
function countSubstringWithEqualEnds(s)
{
var result = 0;
var n = s.length;
// Starting point of substring
for (var i = 0; i < n; i++)
// Length of substring
for (var len = 1; len <= n-i; len++)
// Check if current substring has same
// starting and ending characters.
if (checkEquality(s.substring(i, i + len)))
result++;
return result;
}
// Driver function
var s = "abcab";
document.write(countSubstringWithEqualEnds(s));
// This code contributed by shikhasingrajput
</script>
Producción
7
Aunque el código anterior funciona bien, no es eficiente ya que su complejidad de tiempo es O(n 2 ). Tenga en cuenta que hay n*(n+1)/2 substrings de una string de longitud n. Esta solución también requiere O(n) espacio extra ya que creamos una por una todas las substrings.
Método 2 (espacio eficiente): en este enfoque, en realidad no generamos substrings, sino que recorremos la string de tal manera que podamos comparar fácilmente el primer y el último carácter.
Implementación:
C++
// Space efficient C++ program to count all
// substrings with same first and last characters.
#include <bits/stdc++.h>
using namespace std;
int countSubstringWithEqualEnds(string s)
{
int result = 0;
int n = s.length();
// Iterating through all substrings in
// way so that we can find first and last
// character easily
for (int i=0; i<n; i++)
for (int j=i; j<n; j++)
if (s[i] == s[j])
result++;
return result;
}
// Driver function
int main()
{
string s("abcab");
cout << countSubstringWithEqualEnds(s);
return 0;
}
Java
// Space efficient Java program to count all
// substrings with same first and last characters.
public class GFG {
static int countSubstringWithEqualEnds(String s)
{
int result = 0;
int n = s.length();
// Iterating through all substrings in
// way so that we can find first and last
// character easily
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (s.charAt(i) == s.charAt(j))
result++;
return result;
}
// Driver function
public static void main(String args[])
{
String s = "abcab";
System.out.println(countSubstringWithEqualEnds(s));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Space efficient Python3 program to count all # substrings with same first and last characters. def countSubstringWithEqualEnds(s): result = 0; n = len(s); # Iterating through all substrings in # way so that we can find first and # last character easily for i in range(n): for j in range(i, n): if (s[i] == s[j]): result = result + 1 return result # Driver Code s = "abcab"; print(countSubstringWithEqualEnds(s)) # This code is contributed # by Akanksha Rai
C#
// Space efficient C# program to count all
// substrings with same first and last characters.
using System;
public class GFG {
static int countSubstringWithEqualEnds(string s)
{
int result = 0;
int n = s.Length;
// Iterating through all substrings in
// way so that we can find first and last
// character easily
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (s[i] == s[j])
result++;
return result;
}
// Driver function
public static void Main()
{
string s = "abcab";
Console.Write(countSubstringWithEqualEnds(s));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// Space efficient PHP program to count all
// substrings with same first and last characters.
function countSubstringWithEqualEnds($s)
{
$result = 0;
$n = strlen($s);
// Iterating through all substrings in
// way so that we can find first and last
// character easily
for ($i = 0; $i < $n; $i++)
for ($j = $i; $j < $n; $j++)
if ($s[$i] == $s[$j])
$result++;
return $result;
}
// Driver Code
$s = "abcab";
echo countSubstringWithEqualEnds($s);
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// Space efficient javascript program to count all
// substrings with same first and last characters.
function countSubstringWithEqualEnds(s)
{
var result = 0;
var n = s.length;
// Iterating through all substrings in
// way so that we can find first and last
// character easily
for(i = 0; i < n; i++)
for(j = i; j < n; j++)
if (s.charAt(i) == s.charAt(j))
result++;
return result;
}
// Driver code
var s = "abcab";
document.write(countSubstringWithEqualEnds(s));
// This code is contributed by Princi Singh
</script>
Producción
7
En el código anterior, aunque hemos reducido el espacio extra a O(1), la complejidad del tiempo sigue siendo O(n^2).
Método 3 (mejor enfoque): ahora, si observamos cuidadosamente, podemos darnos cuenta de que la respuesta solo depende de las frecuencias de los caracteres en la string original. Por ejemplo, en la string abcab, la frecuencia de ‘a’ es 2, y las substrings que contribuyen a la respuesta son a, abca y a respectivamente, un total de 3, que se calcula mediante (frecuencia de ‘a’+1) C 2 .
Implementación:
C++
// Most efficient C++ program to count all
// substrings with same first and last characters.
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26; // assuming lower case only
int countSubstringWithEqualEnds(string s)
{
int result = 0;
int n = s.length();
// Calculating frequency of each character
// in the string.
int count[MAX_CHAR] = {0};
for (int i=0; i<n; i++)
count[s[i]-'a']++;
// Computing result using counts
for (int i=0; i<MAX_CHAR; i++)
result += (count[i]*(count[i]+1)/2);
return result;
}
// Driver function
int main()
{
string s("abcab");
cout << countSubstringWithEqualEnds(s);
return 0;
}
Java
// Most efficient Java program to count all
// substrings with same first and last characters.
public class GFG {
// assuming lower case only
static final int MAX_CHAR = 26;
static int countSubstringWithEqualEnds(String s)
{
int result = 0;
int n = s.length();
// Calculating frequency of each character
// in the string.
int[] count = new int[MAX_CHAR];
for (int i = 0; i < n; i++)
count[s.charAt(i)-'a']++;
// Computing result using counts
for (int i = 0; i < MAX_CHAR; i++)
result += (count[i] * (count[i] + 1) / 2);
return result;
}
// Driver function
public static void main(String args[])
{
String s = "abcab";
System.out.println(countSubstringWithEqualEnds(s));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Most efficient Python program to count all
# substrings with same first and last characters.
MAX_CHAR = 26; # assuming lower case only
def countSubstringWithEqualEnds(s):
result = 0;
n = len(s);
# Calculating frequency of each character
# in the string.
count = [0]*MAX_CHAR;
for i in range(n):
count[ord(s[i])-ord('a')]+=1;
# Computing result using counts
for i in range(MAX_CHAR):
result += (count[i]*(count[i]+1)/2);
return result;
# Driver code
s = "abcab";
print(countSubstringWithEqualEnds(s));
# This code is contributed by 29AjayKumar
C#
// Most efficient C# program to count all
// substrings with same first and last characters.
using System;
class GFG {
// assuming lower case only
static readonly int MAX_CHAR = 26;
static int countSubstringWithEqualEnds(String s)
{
int result = 0;
int n = s.Length;
// Calculating frequency of each character
// in the string.
int[] count = new int[MAX_CHAR];
for (int i = 0; i < n; i++)
count[s[i] - 'a']++;
// Computing result using counts
for (int i = 0; i < MAX_CHAR; i++)
result += (count[i] * (count[i] + 1) / 2);
return result;
}
// Driver code
public static void Main()
{
String s = "abcab";
Console.Write(countSubstringWithEqualEnds(s));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// Most efficient PHP program to count all
// substrings with same first and last characters.
$MAX_CHAR = 26; // assuming lower case only
function countSubstringWithEqualEnds($s)
{
global $MAX_CHAR;
$result = 0;
$n = strlen($s);
// Calculating frequency of each
// character in the string.
$count = array_fill(0, $MAX_CHAR, 0);
for ($i = 0; $i < $n; $i++)
$count[ord($s[$i]) - ord('a')]++;
// Computing result using counts
for ($i = 0; $i < $MAX_CHAR; $i++)
$result += ($count[$i] *
($count[$i] + 1) / 2);
return $result;
}
// Driver Code
$s = "abcab";
echo countSubstringWithEqualEnds($s);
// This code is contributed by mits
?>
Javascript
<script>
// Most efficient javascript program to count all
// substrings with same first and last characters.
// assuming lower case only
var MAX_CHAR = 26;
function countSubstringWithEqualEnds(s)
{
var result = 0;
var n = s.length;
// Calculating frequency of each character
// in the string.
var count = Array.from({length: MAX_CHAR}, (_, i) => 0);
for (var i = 0; i < n; i++)
count[s.charAt(i).charCodeAt(0)-'a'.charCodeAt(0)]++;
// Computing result using counts
for (var i = 0; i < MAX_CHAR; i++)
result += (count[i] * (count[i] + 1) / 2);
return result;
}
// Driver function
var s = "abcab";
document.write(countSubstringWithEqualEnds(s));
// This code is contributed by 29AjayKumar
</script>
Producción
7
El código anterior tiene una complejidad de tiempo de O(n) y requiere O(1) espacio extra.
Solución recursiva para contar substrings con los mismos primeros y últimos caracteres
Este artículo es una contribución de Aditya Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA