Número de subsecuencias como “ab” en una string repetida K veces

Dada una String S, considere una nueva string formada repitiendo la S exactamente K veces. Necesitamos encontrar el número de subsecuencias como «ab» en la string recién formada. 

Ejemplos: 

Input : S = "abcb"
        K = 2
Output : 6
Here, Given string is repeated 2 times and
we get a new string "abcbabcb"
Below are 6 occurrences of "ab"
abcbabcb
abcbabcb
abcbabcb
abcbabcb
abcbabcb
abcbabcb

Input : S = "aacbd"
        K = 1
Output : 2

Enfoque ingenuo : encontrar el número de subsecuencias de «ab» es, de hecho, encontrar un par s[i], s[j] (i <j) donde s[i] = ‘a’, s[j] = ‘b’ . 
Podemos hacer esto usando dos bucles for anidados y contar el no. de pares 
Podemos mejorar este enfoque en un solo recorrido de la string. Consideremos un índice j, s[j] =’b’ , si encontramos un número de índices i tal que s[i] = ‘a’ e i < j, entonces es lo mismo que el número de subsecuencias de “ ab” hasta j. Esto se puede hacer manteniendo el conteo de a recorriendo la array y agregando el conteo a nuestra respuesta en la posición donde s[i] =’b . 
Complejidad de tiempo :O(|S|*K)

Enfoque eficiente: 
Sea T la string recién formada 
T = s1 + s2 + s3 + ….. + sk; 
donde si es la i-ésima aparición de la string s. 
Aquí, las ocurrencias de «ab» en T son las siguientes: 
1) «ab» se encuentra completamente en algunas de las ocurrencias de la string S, por lo que simplemente podemos encontrar ocurrencias de «ab» en Si. Sea C. Entonces, total el número de ocurrencias de “ab” en T será C*K .
2) De lo contrario, ”a” se encuentra estrictamente dentro de alguna string Si y “b” se encuentra dentro de alguna otra string Sj, (i < j). De esta manera, encontrar el número de ocurrencias de «ab» será elegir dos ocurrencias de la string S de K ocurrencias ( _KC2) y multiplicarlas por no. de ocurrencias de “a” en Si y número de ocurrencias de “b” en Sj. 
Como, Si = Sj = S. 

Complejidad temporal: O(|S|), para contar el número de «a» y el número de «b».  

// CPP code to find number of subsequences of
// "ab" in the string S which is repeated K times.
#include <bits/stdc++.h>
using namespace std;
 
int countOccurrences(string s, int K)
{
    int n = s.length();
    int C, c1 = 0, c2 = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'a')
            c1++; // Count of 'a's
        if (s[i] == 'b') {
            c2++; // Count of 'b's
            C += c1; // occurrence of "ab"s in string S
        }
    }
 
    // Add following two :
    // 1) K * (Occurrences of "ab" in single string)
    // 2) a is from one string and b is from other.
    return C * K + (K * (K - 1) / 2) * c1 * c2;
}
 
// Driver code
int main()
{
    string S = "abcb";
    int k = 2;
    cout << countOccurrences(S, k) << endl;
    return 0;
}

// Java code to find number of subsequences of
// "ab" in the string S which is repeated K times.
 
import java.io.*;
 
class GFG {
 
    static int countOccurrences(String s, int K)
    {
        int n = s.length();
        int C = 0, c1 = 0, c2 = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'a')
                c1++; // Count of 'a's
            if (s.charAt(i) == 'b') {
                c2++; // Count of 'b's
 
                // occurrence of "ab"s
                // in string S
                C += c1;
            }
        }
 
        // Add following two :
        // 1) K * (Occurrences of "ab" in single string)
        // 2) a is from one string and b is from other.
        return C * K + (K * (K - 1) / 2) * c1 * c2;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String S = "abcb";
        int k = 2;
 
        System.out.println(countOccurrences(S, k));
    }
}
 
// This code is contributed by vt_m.

# Python3 code to find number of
# subsequences of "ab" in the
# string S which is repeated K times.
 
def countOccurrences (s, K):
    n = len(s)
    c1 = 0
    c2 = 0
    C = 0
    for i in range(n):
        if s[i] == 'a':
            c1+= 1 # Count of 'a's
        if s[i] == 'b':
            c2+= 1 # Count of 'b's
             
            # occurrence of "ab"s in string S
            C += c1
             
    # Add following two :
    # 1) K * (Occurrences of "ab" in single string)
    # 2) a is from one string and b is from other.
    return C * K + (K * (K - 1) / 2) * c1 * c2
     
     
# Driver code
S = "abcb"
k = 2
print (countOccurrences(S, k))
 
# This code is contributed by "Abhishek Sharma 44"

// C# code to find number of subsequences
// of "ab" in the string S which is
// repeated K times.
using System;
 
class GFG {
 
    static int countOccurrences(string s, int K)
    {
 
        int n = s.Length;
        int C = 0, c1 = 0, c2 = 0;
 
        for (int i = 0; i < n; i++) {
 
            if (s[i] == 'a')
 
                // Count of 'a's
                c1++;
            if (s[i] == 'b') {
 
                // Count of 'b's
                c2++;
 
                // occurrence of "ab"s
                // in string S
                C += c1;
            }
        }
 
        // Add following two :
        // 1) K * (Occurrences of "ab" in
        // single string)
        // 2) a is from one string and b
        // is from other.
        return C * K + (K * (K - 1) / 2) * c1 * c2;
    }
 
    // Driver code
    public static void Main()
    {
 
        string S = "abcb";
        int k = 2;
 
        Console.WriteLine(
            countOccurrences(S, k));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP code to find number of
// subsequences of "ab" in the
// string S which is repeated K times.
 
function countOccurrences($s, $K)
{
    $n = strlen($s);
    $C = 0; $c1 = 0; $c2 = 0;
    for ($i = 0; $i < $n; $i++)
    {
        if ($s[$i] == 'a')
            // Count of 'a's
            $c1++;
        if ($s[$i] == 'b')
        {
            // Count of 'b's
            $c2++;
             
            // occurrence of "ab"s
            // in string S
            $C = $C+ $c1;
        }
    }
 
    // Add following two :
    // 1) K * (Occurrences of "ab"
    //    in single string)
    // 2) a is from one string and
    //    b is from other.
    return $C * $K + ($K * ($K - 1) / 2) *
                                $c1 * $c2;
}
 
// Driver code
$S = "abcb";
$k = 2;
echo countOccurrences($S, $k), "\n";
 
// This code is contributed by ajit.
?>

<script>
 
// JavaScript code to find number of subsequences of
// "ab" in the string S which is repeated K times.
function countOccurrences(s, K)
{
    let n = s.length;
    let C = 0, c1 = 0, c2 = 0;
     
    for(let i = 0; i < n; i++)
    {
        if (s[i] == 'a')
            c1++; // Count of 'a's
        if (s[i] == 'b')
        {
            c2++; // Count of 'b's
 
            // Occurrence of "ab"s
            // in string S
            C += c1;
        }
    }
 
    // Add following two :
    // 1) K * (Occurrences of "ab" in single string)
    // 2) a is from one string and b is from other.
    return C * K + (K * (K - 1) / 2) * c1 * c2;
}
 
// Driver Code
let S = "abcb";
let k = 2;
 
document.write(countOccurrences(S, k));
 
// This code is contributed by susmitakundugoaldanga
 
</script>

Producción : 

 6 

Complejidad temporal: O(|S|).

Espacio auxiliar: O(|S|)), donde n es la longitud de la string. Esto se debe a que cuando se pasa una string a cualquier función, se pasa por valor y crea una copia de sí mismo en la pila.