You are given two strings s and t of equal length n. You can perform the following operation on the string s:
s of length l where 0 < l < n and append it at the start of s.s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.
Since the answer can be large, return it modulo 109 + 7.
Example 1:
Input: s = "abcd", t = "cdab", k = 2 Output: 2 Explanation: First way: In first operation, choose suffix from index = 3, so resulting s = "dabc". In second operation, choose suffix from index = 3, so resulting s = "cdab". Second way: In first operation, choose suffix from index = 1, so resulting s = "bcda". In second operation, choose suffix from index = 1, so resulting s = "cdab".
Example 2:
Input: s = "ababab", t = "ababab", k = 1 Output: 2 Explanation: First way: Choose suffix from index = 2, so resulting s = "ababab". Second way: Choose suffix from index = 4, so resulting s = "ababab".
Constraints:
2 <= s.length <= 5 * 1051 <= k <= 1015s.length == t.lengths and t consist of only lowercase English alphabets.Problem Overview: You are given two strings s and t. In one operation, a suffix of the current string can be moved to the front, effectively creating a cyclic rotation. The task is to count how many ways the string can become t after exactly k operations.
Approach 1: Cyclic String Rotation with String Matching + DP (O(n + log k) time, O(n) space)
Every operation is a cyclic rotation. Instead of simulating all rotations repeatedly, treat each rotation of s as a state. The key observation: some rotations equal t, others do not. First, concatenate s + s and use a linear string matching algorithm like KMP to count how many rotations match t. This converts the problem into counting transitions between matching and non‑matching rotations over k steps.
Define two states: rotations equal to t and rotations not equal to t. Each operation transitions between these states depending on which rotation is chosen. Use a small dynamic programming recurrence and apply fast matrix exponentiation to compute the number of ways after k operations. String matching takes O(n), and exponentiation runs in O(log k). This approach combines string matching, dynamic programming, and a bit of math for efficient exponentiation.
Approach 2: Direct Character Mapping / Rotation Simulation (O(n^2 * k) time, O(n) space)
A straightforward strategy generates rotations explicitly. For each operation, iterate through all possible suffix choices and construct the resulting rotated string. Compare the result with t and propagate counts using dynamic programming. Each step tracks how many ways each rotation of s can occur.
This approach relies only on basic string manipulation and simple DP transitions. However, generating and comparing rotations repeatedly costs O(n) per rotation, leading to roughly O(n^2) work per step. With k operations, the total complexity becomes impractical for large inputs. It mainly helps verify correctness or build intuition about how rotations transition.
Recommended for interviews: Interviewers expect the rotation + string matching insight. The brute-force rotation simulation demonstrates understanding of the transformation mechanics, but the optimized solution shows algorithmic maturity by combining KMP for rotation detection with matrix exponentiation to handle very large k efficiently.
This approach focuses on understanding the string as a cyclic entity. A string of length n can have one unique permutation per gcd(n, k) based on rotations. By considering these rotations, we can determine whether s can be transformed into t in exactly k operations. We can count the valid rotations that match t.
This C solution uses the gcd (greatest common divisor) function to determine the valid cyclic permutations of the string s that match t. By iterating through possible start indices, we check if the transformed string matches t with the cyclic behavior determined by gcd matches for k.
Time Complexity: O(n2), as for each rotation we compare n characters.
Space Complexity: O(1), as no additional space is used beyond variables.
Another approach involves directly mapping characters from s to t based on their indices. By calculating differences and using modulo arithmetic, we can determine if the string can be rearranged within k operations effectively by focusing on character indices.
This C solution iterates over the characters in s and t and checks for character index matches based on the modulo arithmetic of k operations. As each character aligns correctly with t in rotations, it counts a valid transformation.
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Cyclic String Rotation | Time Complexity: O(n2), as for each rotation we compare n characters. |
| Direct Character Mapping | Time Complexity: O(n) |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Cyclic Rotation + KMP + DP | O(n + log k) | O(n) | Best for large k and long strings. Uses string matching and fast exponentiation. |
| Direct Character Mapping / Rotation Simulation | O(n^2 * k) | O(n) | Useful for understanding transitions or very small constraints. |
2851. String Transformation | Weekly Leetcode 362 • codingMohan • 4,681 views views
Watch 4 more video solutions →Practice String Transformation with our built-in code editor and test cases.
Practice on FleetCode