Given the length N of the string, we have to find the number of special strings of length N.
A string is called a special string if it consists only of lowercase letters a and b and there is at least one b between two a’s in the string. Since the number of strings may be very large, therefore print it modulo 10^9+7.
Examples:
Input: N = 2
Output: 3
Explanation :
The number of special string so length 2 are 3 i.e. “ab”, “ba”, “bb”
Input: N = 3
Output: 5
Explanation:
The number of special string so length 3 are 5 i.e. “abb”, “aba”, “bab”, “bba”, “bbb”
Approach:
To solve the problem mentioned above, the first observation is if the integer N is 0 then there can only be an empty string as the answer, if N is 1 then there can be two string “a” or “b” as an answer but if the value of N is greater than 1 then the answer is equal to the sum of previous two terms. Now to find the count of special strings we run a loop and for each integer i count of the special string of length i is equal to the sum of the count of special strings of length i-1 and count of special strings of length i-2. Store the value of each integer in an array and return the required answer.
Below is the implementation of the above approach:
C++
// C++ Program to Count the number// of Special Strings of a given length N#include <bits/stdc++.h>using namespace std;#define mod 1000000007// Function to return count of special stringslong count_special(long n){ // stores the answer for a // particular value of n long fib[n + 1]; // for n = 0 we have empty string fib[0] = 1; // for n = 1 we have // 2 special strings fib[1] = 2; for (int i = 2; i <= n; i++) { // calculate count of special string of length i fib[i] = (fib[i - 1] % mod + fib[i - 2] % mod) % mod; } // fib[n] stores the count // of special strings of length n return fib[n];}// Driver codeint main(){ // initialise n long n = 3; cout << count_special(n) << endl; return 0;} |
Java
// Java program to count the number of // special strings of a given length Nimport java.util.*;class GFG{ static final int mod = 1000000007;// Function to return count of // special Stringsstatic int count_special(int n){ // Stores the answer for a // particular value of n int []fib = new int[n + 1]; // For n = 0 we have empty String fib[0] = 1; // For n = 1 we have // 2 special Strings fib[1] = 2; for(int i = 2; i <= n; i++) { // Calculate count of special // String of length i fib[i] = (fib[i - 1] % mod + fib[i - 2] % mod) % mod; } // fib[n] stores the count of // special Strings of length n return fib[n];}// Driver codepublic static void main(String[] args){ // Initialise n int n = 3; System.out.print(count_special(n) + "\n");}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to count the number# of special strings of a given length Nmod = 1000000007# Function to return count of # special stringsdef count_special(n): # Stores the answer for a # particular value of n fib = [0 for i in range(n + 1)] # For n = 0 we have empty string fib[0] = 1 # For n = 1 we have # 2 special strings fib[1] = 2 for i in range(2, n + 1, 1): # Calculate count of special # string of length i fib[i] = (fib[i - 1] % mod + fib[i - 2] % mod) % mod # fib[n] stores the count # of special strings of length n return fib[n]# Driver codeif __name__ == '__main__': # Initialise n n = 3 print(count_special(n))# This code is contributed by Bhupendra_Singh |
C#
// C# program to count the number of // special strings of a given length Nusing System;class GFG{ const int mod = 1000000007;// Function to return count of // special Stringsstatic int count_special(int n){ // Stores the answer for a // particular value of n int []fib = new int[n + 1]; // For n = 0 we have empty String fib[0] = 1; // For n = 1 we have // 2 special Strings fib[1] = 2; for(int i = 2; i <= n; i++) { // Calculate count of special // String of length i fib[i] = (fib[i - 1] % mod + fib[i - 2] % mod) % mod; } // fib[n] stores the count of // special Strings of length n return fib[n];}// Driver codepublic static void Main(){ // Initialise n int n = 3; Console.Write(count_special(n) + "\n");}}// This code is contributed by Nidhi_biet |
Javascript
<script> // JavaScript Program to Count the number // of Special Strings of a given length N var mod = 1000000007; // Function to return count of special strings function count_special(n) { // stores the answer for a // particular value of n var fib = [...Array(n + 1)]; // for n = 0 we have empty string fib[0] = 1; // for n = 1 we have // 2 special strings fib[1] = 2; for (var i = 2; i <= n; i++) { // calculate count of special string of length i fib[i] = ((fib[i - 1] % mod) + (fib[i - 2] % mod)) % mod; } // fib[n] stores the count // of special strings of length n return fib[n]; } // Driver code // initialise n var n = 3; document.write(count_special(n) + "<br>"); </script> |
Output:
5
Time Complexity: O(n)
Auxiliary Space: O(n)
Efficient Approach: Space optimization using variables.
In previous approach the fib[i] is depend upon fib[i-1] and fib[i-2] So we can optimize space by storing these 2 values in form of variables where prev1 is fib[i-1] and prev2 is determine fib[i-2]
Implementation Steps:
- Take variable prev1 and prev2 and initialize then with base cases.
- Take another variable curr determine the current computation.
- Iterate over every subproblems and calculate curr from prev1 and prev2.
- After every iteration update prev1 and prev2 for further computation.
- At last return the answer stored in curr.
Implementation:
C++
// C++ Program to Count the number// of Special Strings of a given length N#include <bits/stdc++.h>using namespace std;#define mod 1000000007// Function to return count of special stringslong count_special(long n){ // stores the answer for a // particular value of n int curr; // for n = 0 we have empty string int prev1 =1; // for n = 1 we have // 2 special strings int prev2= 2 ; for (int i = 2; i <= n; i++) { // calculate count of special string of length i curr = (prev1 % mod + prev2 % mod) % mod; prev1 = prev2; prev2 = curr; } // curr stores the count // of special strings of length n return curr;}// Driver codeint main(){ // initialise n long n = 2; cout << count_special(n) << endl; return 0;} |
Java
import java.util.*;public class Main { static final long mod = 1000000007; // Function to return count of special strings static long count_special(long n) { // stores the answer for a // particular value of n long curr = 0; // for n = 0 we have empty string long prev1 = 1; // for n = 1 we have // 2 special strings long prev2 = 2; for (long i = 2; i <= n; i++) { // calculate count of special string of length i curr = (prev1 % mod + prev2 % mod) % mod; prev1 = prev2; prev2 = curr; } // curr stores the count // of special strings of length n return curr; } // Driver code public static void main(String[] args) { // initialise n long n = 2; System.out.println(count_special(n)); }} |
Python3
# Python3 Program to Count the number# of Special Strings of a given length Nmod = 1000000007# Function to return count of special stringsdef count_special(n): # stores the answer for a # particular value of n curr = 0 # for n = 0 we have empty string prev1 = 1 # for n = 1 we have # 2 special strings prev2 = 2 for i in range(2, n+1): # calculate count of special string of length i curr = (prev1 % mod + prev2 % mod) % mod prev1 = prev2 prev2 = curr # curr stores the count # of special strings of length n return curr# Driver coden = 2print(count_special(n)) |
C#
using System;public class GFG{ const int Mod = 1000000007; // Function to return count of special strings static long CountSpecial(long n) { // stores the answer for a // particular value of n int curr = 0; // for n = 0 we have empty string int prev1 = 1; // for n = 1 we have 2 special strings int prev2 = 2; for (int i = 2; i <= n; i++) { // calculate count of special string of length i curr = (prev1 % Mod + prev2 % Mod) % Mod; prev1 = prev2; prev2 = curr; } // curr stores the count // of special strings of length n return curr; } // Driver code public static void Main() { // initialise n long n = 2; Console.WriteLine(CountSpecial(n)); }} |
Javascript
// Function to return count of special stringsconst mod = 1000000007;function count_special(n) { // stores the answer for a // particular value of n let curr; // for n = 0 we have empty string let prev1 = 1; // for n = 1 we have 2 special strings let prev2 = 2; for (let i = 2; i <= n; i++) { // calculate count of special string of length i curr = (prev1 % mod + prev2 % mod) % mod; prev1 = prev2; prev2 = curr; } // curr stores the count // of special strings of length n return curr;}// Driver codelet n = 2;console.log(count_special(n)); |
Output
3
Time Complexity: O(n)
Auxiliary Space: O(1)
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!
