Given string str. The task is to count the number of all different strings possible if two consecutive same characters of the string can be replaced by one different character.
Examples
Input: str = “abclll”
Output: 3
Explanation:
There can be 3 different string including the original string as shown in the below figure:-
Input: str = “abcllldefkkkk”
Output: 15
Explanation:
There can be 15 different string including the original string as shown in the below figure:-
Approach:
The following properties were observed for replacing two equal characters at a time:
- If for string = “aaa” of length 3 we replace two “aa” with one character say “K” then the total number of different possible strings including the original string is:- Ka, aK, aaa. Therefore the number of different strings follows the property of Fibonacci Number of the length of the consecutive characters in the string.
- If string = “aaadefyyyy” then the total number of possible different strings is equaled to the product of combinations of string “aaa” and “yyyy” by replacing the two consecutive characters at a time.
Hence from the above two observations, the count of different possible strings with N consecutive characters is given by N-th Fibonacci Number. Therefore, the total number of different possible strings for the given string str is equal to the product of count of different possible strings for every substring with all same characters.
The following are the steps:
- Count(say cnt) the number of consecutive characters which are same in the given string str.
- To count the different possible strings for the count cnt, find the value of Fibonacci Sequence at cnt.
- Repeat the above steps for all the consecutive characters in the given string str.
- The total count of different possible strings is equaled to the product of all the value of Fibonacci Sequence obtained for every count of consecutive characters.
Below is the implementation of the above approach:
C++
// C++ program to count the// different possible string// form by replacing two same// characters with one#include <bits/stdc++.h>using namespace std;// Array to find the fibonacci// sequenceint fib[100005];// Function to find the// fibonacci sequencevoid computeFibonacci(){ fib[0] = 1; fib[1] = 1; for (int i = 2; i < 100005; i++) { fib[i] = fib[i - 1] + fib[i - 2]; }}// Function to count all// possible stringsint countString(string str){ // Initialize ans = 1 int ans = 1; int cnt = 1; for (int i = 1; str[i]; i++) { // If two consecutive // char are same // increase cnt if (str[i] == str[i - 1]) { cnt++; } // Else multiply the // fib[cnt] to ans // and initialize ans // to 1 else { ans = ans * fib[cnt]; cnt = 1; } } // // If str = abcdeeee, then // for last "eeee" the // count munst be updated ans = ans * fib[cnt]; // Return the total count return ans;}// Driver's Codeint main(){ string str = "abdllldefkkkk"; // Function to precompute // all the fibonacci number computeFibonacci(); // Function call to find // the count cout << countString(str); return 0;} |
Java
// Java program to count the // different possible string // form by replacing two same // characters with one class GFG { // Array to find the fibonacci // sequence static int fib[] = new int[100005]; // Function to find the // fibonacci sequence static void computeFibonacci() { fib[0] = 1; fib[1] = 1; for (int i = 2; i < 100005; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } } // Function to count all // possible strings static int countString(String str) { // Initialize ans = 1 int ans = 1; int cnt = 1; for (int i = 1; i<str.length(); i++) { // If two consecutive // char are same // increase cnt if (str.charAt(i) == str.charAt(i - 1)) { cnt++; } // Else multiply the // fib[cnt] to ans // and initialize ans // to 1 else { ans = ans * fib[cnt]; cnt = 1; } } // If str = abcdeeee, then // for last "eeee" the // count munst be updated ans = ans * fib[cnt]; // Return the total count return ans; } // Driver's Code public static void main (String[] args) { String str = "abdllldefkkkk"; // Function to precompute // all the fibonacci number computeFibonacci(); // Function call to find // the count System.out.println(countString(str)); } }// This code is contributed by Yash_R |
Python3
# Python3 program to count the # different possible string # form by replacing two same # characters with one # Array to find the fibonacci # sequence fib = [0]*100005; # Function to find the # fibonacci sequence def computeFibonacci() : fib[0] = 1; fib[1] = 1; for i in range(2, 100005) : fib[i] = fib[i - 1] + fib[i - 2]; # Function to count all # possible strings def countString(string) : # Initialize ans = 1 ans = 1; cnt = 1; for i in range(1, len(string)) : # If two consecutive # char are same # increase cnt if (string[i] == string[i - 1]) : cnt += 1; # Else multiply the # fib[cnt] to ans # and initialize ans # to 1 else : ans = ans * fib[cnt]; cnt = 1; # If str = abcdeeee, then # for last "eeee" the # count munst be updated ans = ans * fib[cnt]; # Return the total count return ans; # Driver's Code if __name__ == "__main__" : string = "abdllldefkkkk"; # Function to precompute # all the fibonacci number computeFibonacci(); # Function call to find # the count print(countString(string)); # This code is contributed by Yash_R |
C#
// C# program to count the // different possible string // form by replacing two same // characters with one using System;class GFG { // Array to find the fibonacci // sequence static int []fib = new int[100005]; // Function to find the // fibonacci sequence static void computeFibonacci() { fib[0] = 1; fib[1] = 1; for (int i = 2; i < 100005; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } } // Function to count all // possible strings static int countString(string str) { // Initialize ans = 1 int ans = 1; int cnt = 1; for (int i = 1; i < str.Length; i++) { // If two consecutive // char are same // increase cnt if (str[i] == str[i - 1]) { cnt++; } // Else multiply the // fib[cnt] to ans // and initialize ans // to 1 else { ans = ans * fib[cnt]; cnt = 1; } } // If str = abcdeeee, then // for last "eeee" the // count munst be updated ans = ans * fib[cnt]; // Return the total count return ans; } // Driver's Code public static void Main (string[] args) { string str = "abdllldefkkkk"; // Function to precompute // all the fibonacci number computeFibonacci(); // Function call to find // the count Console.WriteLine(countString(str)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript program to count the // different possible string // form by replacing two same // characters with one // Array to find the fibonacci// sequence fib = Array(100005).fill(0); // Function to find the // fibonacci sequence function computeFibonacci() { fib[0] = 1; fib[1] = 1; for (i = 2; i < 100005; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } } // Function to count all // possible strings function countString( str) { // Initialize ans = 1 var ans = 1; var cnt = 1; for (i = 1; i < str.length; i++) { // If two consecutive // char are same // increase cnt if (str.charAt(i) == str.charAt(i - 1)) { cnt++; } // Else multiply the // fib[cnt] to ans // and initialize ans // to 1 else { ans = ans * fib[cnt]; cnt = 1; } } // If str = abcdeeee, then // for last "eeee" the // count munst be updated ans = ans * fib[cnt]; // Return the total count return ans; } // Driver's Code var str = "abdllldefkkkk"; // Function to precompute // all the fibonacci number computeFibonacci(); // Function call to find // the count document.write(countString(str));// This code contributed by umadevi9616</script> |
Output:
15
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(M), where M = 100005
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
