String Transformation - Solution & Explanation

Q: Is String Transformation easy or hard?

String Transformation is classified as a Hard problem. It requires recognizing cyclic rotation behavior, applying a linear string matching algorithm, and optimizing repeated transitions using matrix exponentiation or advanced dynamic programming.

Q: String Transformation Python/Java solution

Implement KMP to count how many cyclic rotations of s match t, then build a 2x2 transition matrix representing valid rotations. Apply fast exponentiation to raise the matrix to the k-th power. The same logic works in Python, Java, C++, and other languages with standard string and matrix operations.

Q: How to solve String Transformation in O(n + log k)?

First compute all rotations of s that match t using KMP on the string s + s. Then model the process as transitions between two states: rotations equal to t and rotations not equal to t. Use matrix exponentiation to apply the transition k times efficiently instead of simulating each step.

Q: What is the best approach for String Transformation?

The most efficient approach treats each operation as a cyclic rotation and uses string matching to detect rotations equal to the target string. KMP finds all valid rotations in O(n) time, and a small dynamic programming state transition is solved using matrix exponentiation in O(log k). This reduces the total complexity to O(n + log k).

Q: Is String Transformation asked at Google/Amazon/Meta?

Hard string and dynamic programming problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of cyclic rotations, string matching algorithms, and optimized DP transitions.

Q: What data structure is used in String Transformation?

The optimized solution mainly relies on arrays for prefix-function computation in KMP, plus a small 2x2 matrix for dynamic programming transitions. The problem combines string algorithms with mathematical DP rather than complex data structures.

Q: What is the time complexity of String Transformation?

The optimized solution runs in O(n + log k) time. O(n) comes from using a linear string matching algorithm such as KMP to find matching rotations, and O(log k) comes from matrix exponentiation used to compute transitions across k operations. Space complexity is O(n).

HardMath String Dynamic Programming String Matching18 min readAsked at: Snowflake, Google, Mathworks

Practice this problem

Problem Statement

You are given two strings s and t of equal length n. You can perform the following operation on the string s:

Remove a suffix of s of length l where 0 < l < n and append it at the start of s.
For example, let 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 10⁹ + 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 * 10⁵
1 <= k <= 10¹⁵
s.length == t.length
s and t consist of only lowercase English alphabets.

Approach Overview

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 1: Cyclic String Rotation

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n²), as for each rotation we compare n characters.
Space Complexity: O(1), as no additional space is used beyond variables.

Try this approach in the editor →

Approach 2: Direct Character Mapping

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Cyclic String Rotation	Time Complexity: O(n²), as for each rotation we compare n characters. Space Complexity: O(1), as no additional space is used beyond variables.
Direct Character Mapping	Time Complexity: O(n) Space Complexity: O(1)
Default Approach	—

Detailed Complexity Analysis

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.

Video Solution

2851. String Transformation | Weekly Leetcode 362 • codingMohan • 4,800 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is String Transformation easy or hard?

String Transformation is classified as a Hard problem. It requires recognizing cyclic rotation behavior, applying a linear string matching algorithm, and optimizing repeated transitions using matrix exponentiation or advanced dynamic programming.

String Transformation Python/Java solution

Implement KMP to count how many cyclic rotations of s match t, then build a 2x2 transition matrix representing valid rotations. Apply fast exponentiation to raise the matrix to the k-th power. The same logic works in Python, Java, C++, and other languages with standard string and matrix operations.

How to solve String Transformation in O(n + log k)?

First compute all rotations of s that match t using KMP on the string s + s. Then model the process as transitions between two states: rotations equal to t and rotations not equal to t. Use matrix exponentiation to apply the transition k times efficiently instead of simulating each step.

What is the best approach for String Transformation?

The most efficient approach treats each operation as a cyclic rotation and uses string matching to detect rotations equal to the target string. KMP finds all valid rotations in O(n) time, and a small dynamic programming state transition is solved using matrix exponentiation in O(log k). This reduces the total complexity to O(n + log k).

Is String Transformation asked at Google/Amazon/Meta?

Hard string and dynamic programming problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of cyclic rotations, string matching algorithms, and optimized DP transitions.

What data structure is used in String Transformation?

The optimized solution mainly relies on arrays for prefix-function computation in KMP, plus a small 2x2 matrix for dynamic programming transitions. The problem combines string algorithms with mathematical DP rather than complex data structures.

What is the time complexity of String Transformation?

The optimized solution runs in O(n + log k) time. O(n) comes from using a linear string matching algorithm such as KMP to find matching rotations, and O(log k) comes from matrix exponentiation used to compute transitions across k operations. Space complexity is O(n).

Ready to solve this problem?

Practice String Transformation with our built-in code editor and test cases.

Practice on FleetCode

Add Two Numbers

Reverse Integer

Problem Info

DifficultyHard

Acceptance27.4%

Approaches3

Reading time18 min

Asked at

Snowflake Google Mathworks

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Cyclic String Rotation

Code

Complexity

Approach 2: Direct Character Mapping

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents