Solución recursiva para contar substrings con los mismos primeros y últimos caracteres

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

Hemos discutido diferentes soluciones en la publicación a continuación.
Contar substrings con los mismos primeros y últimos caracteres

En este artículo, se discute una solución recursiva simple. 

Implementación:

// c++ program to count substrings with same
// first and last characters
#include <iostream>
#include <string>
using namespace std;
 
/* Function to count substrings with same first and
  last characters*/
int countSubstrs(string str, int i, int j, int n)
{
    // base cases
    if (n == 1)
        return 1;
    if (n <= 0)
        return 0;
 
    int res =  countSubstrs(str, i + 1, j, n - 1) + 
               countSubstrs(str, i, j - 1, n - 1) -
               countSubstrs(str, i + 1, j - 1, n - 2);           
 
    if (str[i] == str[j])
        res++;
 
    return res;
}
 
// driver code
int main()
{
    string str = "abcab";
    int n = str.length();
    cout << countSubstrs(str, 0, n - 1, n);
}

// Java program to count substrings
// with same first and last characters
 
class GFG
{
    // Function to count substrings
    // with same first and
    // last characters
    static int countSubstrs(String str, int i,
                                         int j, int n)
    {
        // base cases
        if (n == 1)
            return 1;
        if (n <= 0)
            return 0;
     
        int res = countSubstrs(str, i + 1, j, n - 1) +
                countSubstrs(str, i, j - 1, n - 1) -
                countSubstrs(str, i + 1, j - 1, n - 2);        
     
        if (str.charAt(i) == str.charAt(j))
            res++;
     
        return res;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        String str = "abcab";
        int n = str.length();
        System.out.print(countSubstrs(str, 0, n - 1, n));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python 3 program to count substrings with same
# first and last characters
 
# Function to count substrings with same first and
# last characters
def countSubstrs(str, i, j, n):
 
    # base cases
    if (n == 1):
        return 1
    if (n <= 0):
        return 0
 
    res = (countSubstrs(str, i + 1, j, n - 1)
        + countSubstrs(str, i, j - 1, n - 1)
        - countSubstrs(str, i + 1, j - 1, n - 2))    
 
    if (str[i] == str[j]):
        res += 1
 
    return res
 
# driver code
str = "abcab"
n = len(str)
print(countSubstrs(str, 0, n - 1, n))
 
# This code is contributed by Smitha

// C# program to count substrings
// with same first and last characters
using System;
 
class GFG {
     
    // Function to count substrings
    // with same first and
    // last characters
    static int countSubstrs(string str, int i,
                                 int j, int n)
    {
         
        // base cases
        if (n == 1)
            return 1;
        if (n <= 0)
            return 0;
     
        int res = countSubstrs(str, i + 1, j, n - 1)
                + countSubstrs(str, i, j - 1, n - 1)
            - countSubstrs(str, i + 1, j - 1, n - 2);    
     
        if (str[i] == str[j])
            res++;
     
        return res;
    }
     
    // Driver code
    public static void Main ()
    {
        string str = "abcab";
        int n = str.Length;
         
        Console.WriteLine(
                countSubstrs(str, 0, n - 1, n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to count
// substrings with same
// first and last characters
 
//Function to count substrings
// with same first and
// last characters
function countSubstrs($str, $i,
                      $j, $n)
{
     
    // base cases
    if ($n == 1)
        return 1;
    if ($n <= 0)
        return 0;
 
    $res = countSubstrs($str, $i + 1, $j, $n - 1) +
           countSubstrs($str, $i, $j - 1, $n - 1) -
           countSubstrs($str, $i + 1, $j - 1, $n - 2);    
 
    if ($str[$i] == $str[$j])
        $res++;
 
    return $res;
}
 
// Driver Code
$str = "abcab";
$n = strlen($str);
echo(countSubstrs($str, 0, $n - 1, $n));
 
// This code is contributed by Ajit.
?>

<script>
 
// Javascript program to count substrings
// with same first and last characters
 
// Function to count substrings
// with same first and
// last characters
function countSubstrs(str, i, j, n)
{
       
    // Base cases
    if (n == 1)
        return 1;
    if (n <= 0)
        return 0;
   
    let res = countSubstrs(str, i + 1, j, n - 1) +
              countSubstrs(str, i, j - 1, n - 1) -
          countSubstrs(str, i + 1, j - 1, n - 2);    
   
    if (str[i] == str[j])
        res++;
   
    return res;
}
 
// Driver code
let str = "abcab";
let n = str.length;
 
document.write(countSubstrs(str, 0, n - 1, n));
 
// This code is contributed by rameshtravel07
 
</script>

7

La complejidad temporal de la solución anterior es exponencial. En el peor de los casos, podemos terminar haciendo operaciones O(3 ⁿ ).

Espacio auxiliar:   O(n), donde n es la longitud de la string.

Esto se debe a que cuando se pasa una string en la función, crea una copia de sí mismo en la pila.
 

También hay un enfoque recursivo divide y vencerás

La idea es dividir la string por la mitad hasta que obtengamos un elemento y nuestro caso base devuelva 2 cosas

1. un mapa que contiene el carácter al número de ocurrencias (es decir, a: 1 ya que es el caso base)
2. (Este es el número total de substrings con inicio y fin con el mismo carácter. Dado que el caso base es una string de tamaño uno, comienza y termina con el mismo carácter)

Luego combine las soluciones de la división izquierda y derecha de la string, luego devuelva una nueva solución basada en izquierda y derecha. Esta nueva solución se puede construir multiplicando los caracteres comunes entre el conjunto izquierdo y derecho y sumando el recuento de soluciones de izquierda a derecha, y devolviendo un mapa que contiene el recuento de ocurrencias de elementos y el recuento de soluciones.

Implementación:

# code
def countSubstr(s):
    if len(s) == 0:
        return 0
    charMap, numSubstr = countSubstrHelper(s, 0, len(s)-1)
    return numSubstr
 
 
def countSubstrHelper(string, start, end):
    if start >= end:  # our base case for the recursion. When we have one character
        return {string[start]: 1}, 1
    mid = (start + end)//2
    mapLeft, numSubstrLeft = countSubstrHelper(
        string, start, mid)  # solve the left half
    mapRight, numSubstrRight = countSubstrHelper(
        string, mid+1, end)  # solve the right half
    # add number of substrings from left and right
    numSubstrSelf = numSubstrLeft + numSubstrRight
 
    # multiply the characters from left set with matching characters from right set
    # then add to total number of substrings
    for char in mapLeft:
        if char in mapRight:
            numSubstrSelf += mapLeft[char] * mapRight[char]
 
    # Add all the key,value pairs from right map to left map
    for char in mapRight:
        if char in mapLeft:
            mapLeft[char] += mapRight[char]
        else:
            mapLeft[char] = mapRight[char]
    # Return the map of character and the sum of substring from left, right and self
    return mapLeft, numSubstrSelf
 
 
print(countSubstr("abcab"))
 
# Contributed by Xavier Jean Baptiste

7

La complejidad temporal de la solución anterior es O(nlogn) con complejidad espacial O(n) que ocurre si todos los elementos son distintos

Este artículo es una contribución de Yash Singla . 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.