Given two strings S and T and a number K, the task is to count the number of ways to convert string S to string T by performing K cyclic shifts.
The cyclic shift is defined as the string S can be split into two non-empty parts X + Y and in one operation we can transform S to Y + X from X + Y.
Note: Since count can be very large print the answer to modulo 109 + 7.
Examples:
Input: S = “ab”, T = “ab”, K = 2
Output: 1
Explanation:
The only way to do this is to convert [ab to ba] in the first move and then [ba to ab] in the second move.
Input: S = “ababab”, T = “ababab”, K = 1
Output: 2
Explanation:
One possible way to convert S to T in one move is [ab | abab] -> [ababab], the second way is [abab | ab] -> [ababab]. So there are total two ways.
Approach: This problem can be solved using Dynamic Programming. Let us call a cyclic shift ‘good’ if at the end we are at string T and the vice versa for ‘bad’. Below are the steps:
- Precompute the number of good(denoted by a) and bad(denoted by b) cyclic shifts.
- Initialize two dp arrays such that dp1[i] denote the number of ways to get to a good shift in i moves and dp2[i] denotes the number of ways to get to a bad shift in i moves.
- For transition, we are only concerned about previous state i.e., (i – 1)th state and the answer to this question is dp1[K].
- So the number of ways to reach a good state in i moves is equal to the number of ways of reaching a good shift in i-1 moves multiplied by (a-1) (as last shift is also good)
- So the number of ways of reaching a bad shift in i-1 moves multiplied by (a)(as next move can be any of the good shifts).
Below is the recurrence relation for the good and bad shifts:
So for good shifts we have:
Similarly, for bad shifts we have:
![dp1[i]= dp1[i-1]*(a-1) + dp2[i-1]*a](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-7478367ccc4c8011946dd7b61b92977d_l3.png "Rendered by QuickLaTeX.com")
![dp2[i]=dp1[i-1]*b + dp2[i-1]*(b-1)](https://geeksforgeeks.org/wp-content/uploads/2023/10/rubhabha_quicklatex.com-f1f688e09146ae79fb6be5d24374f77c_l3.png "Rendered by QuickLaTeX.com")
Below is the implementation of above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define mod 10000000007 // Function to count number of ways to // convert string S to string T by // performing K cyclic shifts long long countWays(string s, string t, int k) { // Calculate length of string int n = s.size(); // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0, b = 0; // Iterate in the string for (int i = 0; i < n; i++) { string p = s.substr(i, n - i) + s.substr(0, i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // Initialize two dp arrays // dp1[i] to store the no of ways to // get to a good shift in i moves // dp2[i] to store the no of ways to // get to a bad shift in i moves vector<long long> dp1(k + 1), dp2(k + 1); if (s == t) { dp1[0] = 1; dp2[0] = 0; } else { dp1[0] = 0; dp2[0] = 1; } // Calculate good and bad shifts for (int i = 1; i <= k; i++) { dp1[i] = ((dp1[i - 1] * (a - 1)) % mod + (dp2[i - 1] * a) % mod) % mod; dp2[i] = ((dp1[i - 1] * (b)) % mod + (dp2[i - 1] * (b - 1)) % mod) % mod; } // Return the required number of ways return dp1[k]; } // Driver Code int main() { // Given Strings string S = "ab", T = "ab"; // Given K shifts required int K = 2; // Function Call cout << countWays(S, T, K); return 0; } |
Java
// Java program for above approach class GFG{ static long mod = 10000000007L; // Function to count number of ways to // convert string S to string T by // performing K cyclic shifts static long countWays(String s, String t, int k) { // Calculate length of string int n = s.length(); // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0, b = 0; // Iterate in the string for(int i = 0; i < n; i++) { String p = s.substring(i, n - i) + s.substring(0, i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // Initialize two dp arrays // dp1[i] to store the no of ways to // get to a good shift in i moves // dp2[i] to store the no of ways to // get to a bad shift in i moves long dp1[] = new long[k + 1]; long dp2[] = new long[k + 1]; if (s == t) { dp1[0] = 1; dp2[0] = 0; } else { dp1[0] = 0; dp2[0] = 1; } // Calculate good and bad shifts for(int i = 1; i <= k; i++) { dp1[i] = ((dp1[i - 1] * (a - 1)) % mod + (dp2[i - 1] * a) % mod) % mod; dp2[i] = ((dp1[i - 1] * (b)) % mod + (dp2[i - 1] * (b - 1)) % mod) % mod; } // Return the required number of ways return dp1[k]; } // Driver code public static void main(String[] args) { // Given Strings String S = "ab", T = "ab"; // Given K shifts required int K = 2; // Function Call System.out.print(countWays(S, T, K)); } } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approach mod = 1000000007# Function to count number of ways # to convert string S to string T by # performing K cyclic shifts def countWays(s, t, k): # Calculate length of string n = len(s) # a is no. of good cyclic shifts # b is no. of bad cyclic shifts a = 0 b = 0 # Iterate in string for i in range(n): p = s[i : ] + s[: i] # Precompute the number of good # and bad cyclic shifts if(p == t): a += 1 else: b += 1 # Initialize two dp arrays # dp1[i] to store the no of ways to # get to a goof shift in i moves # dp2[i] to store the no of ways to # get to a bad shift in i moves dp1 = [0] * (k + 1) dp2 = [0] * (k + 1) if(s == t): dp1[0] = 1 dp2[0] = 0 else: dp1[0] = 0 dp2[0] = 1 # Calculate good and bad shifts for i in range(1, k + 1): dp1[i] = ((dp1[i - 1] * (a - 1)) % mod + (dp2[i - 1] * a) % mod) % mod dp2[i] = ((dp1[i - 1] * (b)) % mod + (dp2[i - 1] * (b - 1)) % mod) % mod # Return the required number of ways return(dp1[k]) # Driver Code # Given Strings S = 'ab'T = 'ab'# Given K shifts required K = 2# Function call print(countWays(S, T, K)) # This code is contributed by Arjun Saini |
C#
// C# program for the above approachusing System;class GFG{ static long mod = 10000000007L;// Function to count number of ways to// convert string S to string T by// performing K cyclic shiftsstatic long countWays(string s, string t, int k){ // Calculate length of string int n = s.Length; // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0, b = 0; // Iterate in the string for(int i = 0; i < n; i++) { string p = s.Substring(i, n - i) + s.Substring(0, i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // Initialize two dp arrays // dp1[i] to store the no of ways to // get to a good shift in i moves // dp2[i] to store the no of ways to // get to a bad shift in i moves long []dp1 = new long[k + 1]; long []dp2 = new long[k + 1]; if (s == t) { dp1[0] = 1; dp2[0] = 0; } else { dp1[0] = 0; dp2[0] = 1; } // Calculate good and bad shifts for(int i = 1; i <= k; i++) { dp1[i] = ((dp1[i - 1] * (a - 1)) % mod + (dp2[i - 1] * a) % mod) % mod; dp2[i] = ((dp1[i - 1] * (b)) % mod + (dp2[i - 1] * (b - 1)) % mod) % mod; } // Return the required number of ways return dp1[k];}// Driver code public static void Main(string[] args) { // Given Strings string S = "ab", T = "ab"; // Given K shifts required int K = 2; // Function call Console.Write(countWays(S, T, K)); } } // This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript program for the above approachlet mod = 10000000007; // Function to count number of ways to // convert string S to string T by // performing K cyclic shifts function countWays(s, t, k) { // Calculate length of string let n = s.length; // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts let a = 0, b = 0; // Iterate in the string for(let i = 0; i < n; i++) { let p = s.substr(i, n - i) + s.substr(0, i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // Initialize two dp arrays // dp1[i] to store the no of ways to // get to a good shift in i moves // dp2[i] to store the no of ways to // get to a bad shift in i moves let dp1 = Array.from({length: k+1}, (_, i) => 0); let dp2 = Array.from({length: k+1}, (_, i) => 0); if (s == t) { dp1[0] = 1; dp2[0] = 0; } else { dp1[0] = 0; dp2[0] = 1; } // Calculate good and bad shifts for(let i = 1; i <= k; i++) { dp1[i] = ((dp1[i - 1] * (a - 1)) % mod + (dp2[i - 1] * a) % mod) % mod; dp2[i] = ((dp1[i - 1] * (b)) % mod + (dp2[i - 1] * (b - 1)) % mod) % mod; } // Return the required number of ways return dp1[k]; } // Driver Code // Given Strings let S = "ab", T = "ab"; // Given K shifts required let K = 2; // Function Call document.write(countWays(S, T, K)); </script> |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(K)
Efficient approach: Space optimization O(1)
In the previous approach, the current values dp1[i] and dp2[i] only depend upon the previous value i.e. dp1[i-1] and dp2[i-1]. So to optimize the space we can keep track of previous and current values with the help of 2 variables prev and curr which will reduce the space complexity from O(k) to O(1).
Steps to implement the above approach:
- Create 2 variables for both array dp1_prev and dp2_prev to keep track o previous values of dp1 and dp2.
- Initialize base case dp1_prev and dp2_prev.
- Create a variable current for both dp1_curr and dp2_curr to store the current value.
- Iterate over the subproblem using a loop and update both current values.
- After every iteration update dp1_prev and dp2_prev for further iterations.
- At last return dp1_curr.
Below is the code to implement the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define mod 10000000007// Function to count number of ways to// convert string S to string T by// performing K cyclic shiftslong long countWays(string s, string t, int k){ // Calculate length of string int n = s.size(); // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0, b = 0; // Iterate in the string for (int i = 0; i < n; i++) { string p = s.substr(i, n - i) + s.substr(0, i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // initialize variables for current and previous values // of DP1 and DP2 int dp1_curr, dp1_prev, dp2_curr, dp2_prev; // Base Case if (s == t) { dp1_prev = 1; dp2_prev = 0; } else { dp1_prev = 0; dp2_prev = 1; } // Iterate over subproblems and update current values for (int i = 1; i <= k; i++) { dp1_curr = ((dp1_prev * (a - 1)) % mod + (dp2_prev * a) % mod) % mod; dp2_curr = ((dp1_prev * (b)) % mod + (dp2_prev * (b - 1)) % mod) % mod; // assigning values for iterating further dp1_prev = dp1_curr; dp2_prev = dp2_curr; } // return final answer return dp1_curr;}// Driver Codeint main(){ // Given Strings string S = "ab", T = "ab"; // Given K shifts required int K = 2; // Function Call cout << countWays(S, T, K); return 0;} |
Java
import java.util.*;public class Main { static long mod = 10000000007L; public static long countWays(String s, String t, int k) { // Calculate length of string int n = s.length(); // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0, b = 0; // Iterate in the string for (int i = 0; i < n; i++) { String p = s.substring(i, n) + s.substring(0, i); // Precompute the number of good // and bad cyclic shifts if (p.equals(t)) a++; else b++; } // initialize variables for current and previous values // of DP1 and DP2 long dp1_curr = 0, dp1_prev, dp2_curr = 0, dp2_prev; // Base Case if (s.equals(t)) { dp1_prev = 1; dp2_prev = 0; } else { dp1_prev = 0; dp2_prev = 1; } // Iterate over subproblems and update current values for (int i = 1; i <= k; i++) { dp1_curr = ((dp1_prev * (a - 1)) % mod + (dp2_prev * a) % mod) % mod; dp2_curr = ((dp1_prev * b) % mod + (dp2_prev * (b - 1)) % mod) % mod; // assigning values for iterating further dp1_prev = dp1_curr; dp2_prev = dp2_curr; } // return final answer return dp1_curr; } public static void main(String[] args) { // Given Strings String S = "ab", T = "ab"; // Given K shifts required int K = 2; // Function Call System.out.println(countWays(S, T, K)); }} |
Python3
MOD = 10**9 + 7 # Define a constant for modulo arithmeticdef countWays(s, t, k): n = len(s) a, b = 0, 0 # Initialize counts of good and bad cyclic shifts # Iterate over all cyclic shifts of s and count good and bad ones for i in range(n): p = s[i:] + s[:i] # Compute the i-th cyclic shift of s if p == t: a += 1 else: b += 1 # Initialize variables for DP dp1_prev, dp2_prev = (1, 0) if s == t else (0, 1) dp1_curr, dp2_curr = 0, 0 # Iterate over subproblems and update DP values for i in range(1, k+1): dp1_curr = ((dp1_prev * (a - 1)) % MOD + (dp2_prev * a) % MOD) % MOD dp2_curr = ((dp1_prev * b) % MOD + (dp2_prev * (b - 1)) % MOD) % MOD # Update previous values for next iteration dp1_prev, dp2_prev = dp1_curr, dp2_curr return dp1_curr# Example usageS = 'ab'T = 'ab'K = 2print(countWays(S, T, K)) |
C#
using System;public class MainClass { static long mod = 10000000007L; public static long countWays(string s, string t, int k) { // Calculate length of string int n = s.Length; // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0, b = 0; // Iterate in the string for (int i = 0; i < n; i++) { string p = s.Substring(i, n - i) + s.Substring(0, i); // Precompute the number of good // and bad cyclic shifts if (p.Equals(t)) a++; else b++; } // initialize variables for current and previous values // of DP1 and DP2 long dp1_curr = 0, dp1_prev, dp2_curr = 0, dp2_prev; // Base Case if (s.Equals(t)) { dp1_prev = 1; dp2_prev = 0; } else { dp1_prev = 0; dp2_prev = 1; } // Iterate over subproblems and update current values for (int i = 1; i <= k; i++) { dp1_curr = ((dp1_prev * (a - 1)) % mod + (dp2_prev * a) % mod) % mod; dp2_curr = ((dp1_prev * b) % mod + (dp2_prev * (b - 1)) % mod) % mod; // assigning values for iterating further dp1_prev = dp1_curr; dp2_prev = dp2_curr; } // return final answer return dp1_curr; } public static void Main() { // Given Strings string S = "ab", T = "ab"; // Given K shifts required int K = 2; // Function Call Console.WriteLine(countWays(S, T, K)); }} |
Javascript
// Define a constant for modulo arithmeticconst MOD = 1000000007;function countWays(s, t, k) { const n = s.length; // Initialize counts of good and bad cyclic shifts let a = 0, b = 0; // Iterate over all cyclic shifts of s and count good and bad ones for (let i = 0; i < n; i++) { // Compute the i-th cyclic shift of s const p = s.slice(i) + s.slice(0, i); if (p === t) { a += 1; } else { b += 1; } } // Initialize variables for DP let dp1_prev, dp2_prev; if (s === t) { dp1_prev = 1; dp2_prev = 0; } else { dp1_prev = 0; dp2_prev = 1; } let dp1_curr = 0, dp2_curr = 0; // Iterate over subproblems and update DP values for (let i = 1; i <= k; i++) { dp1_curr = ((dp1_prev * (a - 1)) % MOD + (dp2_prev * a) % MOD) % MOD; dp2_curr = ((dp1_prev * b) % MOD + (dp2_prev * (b - 1)) % MOD) % MOD; // Update previous values for the next iteration dp1_prev = dp1_curr; dp2_prev = dp2_curr; } return dp1_curr;}// Example usageconst S = 'ab';const T = 'ab';const K = 2;console.log(countWays(S, T, K));// This code is contributed by Samim Hossain Mondal. |
Output
1
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!
