Find number of Strictly Increasing Sequences with ‘a’ and ‘b’ in a String
Given a string S of length N (1 <= N <= 105) consisting of lower case alphabets. The task is to find the number of strictly increasing sequences P1,P2, …, Pk such that:
- For each i (1 ≤ i ≤ k), Spi = ‘a’
- For each i (1 ≤ i < k), there exists j such that pi < j < pi+1 and Sj = ‘b’
The result should be calculated modulo 10^9 + 7.
Example:
Input: s = “abbaa”
Output: 5Input: s = “baaaa”
Output: 4
Approach:
The idea is to use a greedy approach to solve this problem. Maintains two variables, result and temp, where result stores the current number of strictly increasing sequences ending with ‘a’ and temp stores the number of strictly increasing sequences ending with ‘a’ before the last ‘b’ was encountered.
Iterates over each character in the string
- Check if the character is ‘a’, then increments result by temp + 1. The +1 is for the sequence ending at the current ‘a’, and temp adds the sequences that can be formed by appending the current ‘a’ to all sequences ending with ‘a’ before the last ‘b’.
- If the character is ‘b’, it updates temp to result, preparing for the next ‘a’ characters.
Finally, the result is the total number of strictly increasing sequences ending with ‘a’.
Steps-by-step apprach:
- Set result and temp to 0. These variables will be used to keep track of the final result and a temporary value.
- Loop through each character in the given string (s).
- Check for ‘a’: Inside the loop, if the current character is ‘a’, update the result using the formula (result + temp + 1) % 1000000007.
- Check for ‘b’: If the current character is ‘b’, update the temp value using the result.
- After iterating through the string, return the final result
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int solve(string & s) { // Variables to store the result and a temporary value int result = 0, temp = 0; // Iterate over each character in the string for ( int i = 0; i < s.size(); i++) { // If the character is 'a', update the result if (s[i] == 'a' ) result = (result + temp + 1) % 1000000007; // If the character is 'b', update the temporary // value if (s[i] == 'b' ) temp = result; } // Return the result return result; } int main() { // Input string string s = "abbaa" ; cout << solve(s); return 0; } |
Java
public class LexicographicallyLargest { public static int solve(String s) { // Variables to store the result and a temporary // value int result = 0 , temp = 0 ; // Iterate over each character in the string for ( int i = 0 ; i < s.length(); i++) { // If the character is 'a', update the result if (s.charAt(i) == 'a' ) result = (result + temp + 1 ) % 1000000007 ; // If the character is 'b', update the temporary // value if (s.charAt(i) == 'b' ) temp = result; } // Return the result return result; } public static void main(String[] args) { // Input string String s = "abbaa" ; System.out.println(solve(s)); } } |
Python3
def solve(s): # Variables to store the result and a temporary value result = 0 temp = 0 # Iterate over each character in the string for char in s: # If the character is 'a', update the result if char = = 'a' : result = (result + temp + 1 ) % 1000000007 # If the character is 'b', update the temporary value if char = = 'b' : temp = result # Return the result return result #Driver code s = "abbaa" # Print the result of the solve function print (solve(s)) |
C#
using System; class Program { static int Solve( string s) { // Variables to store the result and a temporary // value int result = 0, temp = 0; // Iterate over each character in the string for ( int i = 0; i < s.Length; i++) { // If the character is 'a', update the result if (s[i] == 'a' ) result = (result + temp + 1) % 1000000007; // If the character is 'b', update the temporary // value if (s[i] == 'b' ) temp = result; } // Return the result return result; } static void Main() { // Input string string s = "abbaa" ; Console.WriteLine(Solve(s)); } } |
Javascript
// JavaScript Implementation function solve(s) { let result = 0; let temp = 0; for (let i = 0; i < s.length; i++) { if (s[i] === 'a' ) { result = (result + temp + 1) % 1000000007; } if (s[i] === 'b' ) { temp = result; } } return result; } const s = "abbaa" ; console.log(solve(s)); // This code is contributed by Tapesh(tapeshdu420) |
5
Time Complexity: O(N), where N is the length of the input string.
Auxiliary Space: O(1)