Cuente todas las strings posibles que se pueden generar colocando espacios

Dada una string S , la tarea es contar todas las strings posibles que se pueden generar colocando espacios entre cualquier par de caracteres adyacentes de la string.

Ejemplos:

Entrada: S = “AB”
Salida: 2
Explicación: Todas las strings posibles son { “AB”, “AB”}.

Entrada: S = “ABC”
Salida: 4
Explicación: Todas las strings posibles son {“A BC”, “AB C”, “ABC”, “ABC”}

Enfoque: el problema se puede resolver asumiendo que los espacios entre pares de caracteres adyacentes de la string son bits binarios. Generalmente, si la longitud de la string es L , entonces hay L – 1 lugares para llenar con espacios.

Ilustración: 

S = “ABCD” 
Los lugares posibles para los espacios son: 

• Entre A y B»
• Entre «B» y «C»
• Entre «C» y «D»

Longitud de la string = 4 
Espacios posibles para espacios = 3 = 4 – 1
Suponiendo que cada lugar sea un bit binario, el número total de combinaciones posibles es: 

1. 000 -> “ABCD”
2. 001 -> “ABC D”
3. 010 -> “CD AB”
4. 011 -> “CD AB”
5. 100 -> “UN BCD”
6. 101 -> “AB D”
7. 110 -> “CD AB”
8. 111 -> “ABCD”

Por lo tanto, se pueden obtener 8 strings posibles para una string de longitud 4.
Por lo tanto, el recuento total de strings = 2 ^{L – 1} 
 

A continuación se muestra la implementación de la idea anterior: 

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
 
long long int countNumberOfStrings(string s)
{
 
    // Length of the string
    int length = s.length();
 
    // Count of positions for spaces
    int n = length - 1;
 
    // Count of possible strings
    long long int count = pow(2, n);
 
    return count;
}
 
// Driver Code
int main()
{
    string S = "ABCD";
    cout << countNumberOfStrings(S);
 
    return 0;
}

// C program to implement
// the above approach
#include <math.h>
#include <stdio.h>
#include <string.h>
 
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
long long int countNumberOfStrings(char* s)
{
     
    // Length of the string
    int length = strlen(s);
 
    // Count of positions for spaces
    int n = length - 1;
 
    // Count of possible strings
    long long int count = pow(2, n);
 
    return count;
}
 
// Driver Code
int main()
{
    char S[] = "ABCD";
    printf("%lld", countNumberOfStrings(S));
 
    return 0;
}
 
// This code is contributed by single__loop

// Java program to implement
// the above approach
import java.io.*;
 
class GFG{
     
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
static long countNumberOfStrings(String s)
{
     
    // Count of positions for spaces
    int n = s.length() - 1;
     
    // Count of possible strings
    long count = (long)(Math.pow(2, n));
 
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "ABCD";
     
    System.out.println(countNumberOfStrings(S));
}
}
 
// This code is contributed by single__loop

# Python3 program to implement
# the above approach
 
# Function to count the number of strings
# that can be generated by placing spaces
# between pair of adjacent characters
def countNumberOfStrings(s):
     
    # Length of the string
    length = len(s)
     
    # Count of positions for spaces
    n = length - 1
     
    # Count of possible strings
    count = 2 ** n
 
    return count
 
# Driver Code
if __name__ == "__main__" :
 
    S = "ABCD"
     
    print(countNumberOfStrings(S))
     
# This code is contributed by AnkThon

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
static long countNumberOfStrings(String s)
{
     
    // Count of positions for spaces
    int n = s.Length - 1;
     
    // Count of possible strings
    long count = (long)(Math.Pow(2, n));
 
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
    string S = "ABCD";
     
    Console.WriteLine(countNumberOfStrings(S));
}
}
 
// This code is contributed by AnkThon

<script>
 
// JavaScript program for above approach
 
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
function countNumberOfStrings(s)
{
      
    // Count of positions for spaces
    let n = s.length - 1;
      
    // Count of possible strings
    let count = (Math.pow(2, n));
  
    return count;
}
 
// Driver Code
     let S = "ABCD";
    document.write(countNumberOfStrings(S));
   
  // This code is contributed by avijitmondal1998.
</script>

8

Complejidad de tiempo: O(log (len – 1)), donde len representa la longitud de la string dada.  
Espacio Auxiliar: O(1)