Watch 5 video solutions for String Transformation, a hard level problem involving Math, String, Dynamic Programming. This walkthrough by codingMohan has 4,681 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |