2851. String Transformation - Solution

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).

The problem

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.

Python

import math

MODULO = 1000000007

def count_transformations(s, t, k):
    n = len(s)
    count = 0
    for i in range(n):
        match = True
        for j in range(n):
            if s[(i+j) % n] != t[j]:
                match = False
                break
        if match and k % math.gcd(n, i) == 0:
            count = (count + 1) % MODULO
    return count

s = "abcd"
t = "cdab"
k = 2
print(count_transformations(s, t, k))

Java

import java.util.Scanner;

public class Main {
    private static final int MODULO = 1000000007;

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private static int countTransformations(String s, String t, int k) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            boolean match = true;
            for (int j = 0; j < n; j++) {
                if (s.charAt((i + j) % n) != t.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match && k % gcd(n, i) == 0) {
                count = (count + 1) % MODULO;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s = "abcd";
        String t = "cdab";
        int k = 2;
        System.out.println(countTransformations(s, t, k));
    }
}

C++

#include <iostream>
#include <string>
#include <numeric>
#define MODULO 1000000007

using namespace std;

int countTransformations(const string &s, const string &t, int k) {
    int n = s.length();
    int count = 0;
    for (int i = 0; i < n; i++) {
        bool match = true;
        for (int j = 0; j < n; j++) {
            if (s[(i + j) % n] != t[j]) {
                match = false;
                break;
            }
        }
        if (match && k % gcd(n, i) == 0) {
            count = (count + 1) % MODULO;
        }
    }
    return count;
}

int main() {
    string s = "abcd";
    string t = "cdab";
    int k = 2;
    cout << countTransformations(s, t, k) << endl;
    return 0;
}

JavaScript

const MODULO = 1000000007;

function gcd(a, b) {
    while (b) {
        [a, b] = [b, a % b];
    }
    return a;
}

function countTransformations(s, t, k) {
    const n = s.length;
    let count = 0;
    for (let i = 0; i < n; i++) {
        let match = true;
        for (let j = 0; j < n; j++) {
            if (s[(i + j) % n] !== t[j]) {
                match = false;
                break;
            }
        }
        if (match && k % gcd(n, i) === 0) {
            count = (count + 1) % MODULO;
        }
    }
    return count;
}

console.log(countTransformations("abcd", "cdab", 2));

#include <stdio.h>
#include <string.h>
#define MODULO 1000000007

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int countTransformations(const char *s, const char *t, int k, int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        int match = 1;
        for (int j = 0; j < n; j++) {
            if (s[(i + j) % n] != t[j]) {
                match = 0;
                break;
            }
        }
        if (match && k % gcd(n, i) == 0) {
            count = (count + 1) % MODULO;
        }
    }
    return count;
}

int main() {
    char s[] = "abcd";
    char t[] = "cdab";
    int k = 2;
    int n = strlen(s);
    printf("%d\n", countTransformations(s, t, k, n));
    return 0;
}

using System;

class Program {
    const int MODULO = 1000000007;

    static int Gcd(int a, int b) {
        return b == 0 ? a : Gcd(b, a % b);
    }

    static int CountTransformations(string s, string t, int k) {
        int n = s.Length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            bool match = true;
            for (int j = 0; j < n; j++) {
                if (s[(i + j) % n] != t[j]) {
                    match = false;
                    break;
                }
            }
            if (match && k % Gcd(n, i) == 0) {
                count = (count + 1) % MODULO;
            }
        }
        return count;
    }

    static void Main() {
        string s = "abcd";
        string t = "cdab";
        int k = 2;
        Console.WriteLine(CountTransformations(s, t, k));
    }
}

This Python code calculates the number of cyclic permutations of s that can be formed by using the gcd. For each possible rotation starting point, it checks if the transformation matches t.

Complexity

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

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.

Python

MOD = 1000000007

def ways_to_transform(s, t, k):
    n = len(s)
    possible_ways = 0
    for i in range(n):
        mapping_shift = (ord(s[i]) - ord(t[i]) + n) % n
        if k % n == mapping_shift:
            possible_ways = (possible_ways + 1) % MOD
    return possible_ways

s = "abcd"
t = "cdab"
k = 2
print(ways_to_transform(s, t, k))

Java

public class Main {
    private static final int MOD = 1000000007;

    private static int waysToTransform(String s, String t, long k) {
        int n = s.length();
        long possibleWays = 0;
        for (int i = 0; i < n; ++i) {
            int mappingShift = (s.charAt(i) - t.charAt(i) + n) % n;
            if (k % n == mappingShift) {
                possibleWays = (possibleWays + 1) % MOD;
            }
        }
        return (int) possibleWays;
    }

    public static void main(String[] args) {
        String s = "abcd";
        String t = "cdab";
        long k = 2;
        System.out.println(waysToTransform(s, t, k));
    }
}

C++

#include <iostream>
#include <string>
#define MOD 1000000007

using namespace std;

int waysToTransform(const string &s, const string &t, long long k) {
    int n = s.size();
    long long possibleWays = 0;
    for (int i = 0; i < n; ++i) {
        int mappingShift = (s[i] - t[i] + n) % n;
        if (k % n == mappingShift) {
            possibleWays = (possibleWays + 1) % MOD;
        }
    }
    return possibleWays;
}

int main() {
    string s = "abcd";
    string t = "cdab";
    long long k = 2;
    cout << waysToTransform(s, t, k) << endl;
    return 0;
}

JavaScript

const MOD = 1000000007;

function waysToTransform(s, t, k) {
    const n = s.length;
    let possibleWays = 0;
    for (let i = 0; i < n; ++i) {
        const mappingShift = (s.charCodeAt(i) - t.charCodeAt(i) + n) % n;
        if (k % n === mappingShift) {
            possibleWays = (possibleWays + 1) % MOD;
        }
    }
    return possibleWays;
}

console.log(waysToTransform("abcd", "cdab", 2));

#include <stdio.h>
#include <string.h>
#define MOD 1000000007

int waysToTransform(char *s, char *t, long long k) {
    int n = strlen(s);
    long long possibleWays = 0;
    for (int i = 0; i < n; ++i) {
        int mappingShift = (s[i] - t[i] + n) % n;
        if (k % n == mappingShift) {
            possibleWays = (possibleWays + 1) % MOD;
        }
    }
    return possibleWays;
}

int main() {
    char s[] = "abcd";
    char t[] = "cdab";
    long long k = 2;
    printf("%d\n", waysToTransform(s, t, k));
    return 0;
}

using System;

class Program {
    const int MOD = 1000000007;

    static int WaysToTransform(string s, string t, long k) {
        int n = s.Length;
        long possibleWays = 0;
        for (int i = 0; i < n; ++i) {
            int mappingShift = (s[i] - t[i] + n) % n;
            if (k % n == mappingShift) {
                possibleWays = (possibleWays + 1) % MOD;
            }
        }
        return (int)possibleWays;
    }

    static void Main() {
        string s = "abcd";
        string t = "cdab";
        long k = 2;
        Console.WriteLine(WaysToTransform(s, t, k));
    }
}

This Python example counts how many times feasible transformations align when cyclic rotations pivot within each modulo-derived condition matching t's layout.

Complexity

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

Try this approach in the editor

Complexity comparison

Approach	Complexity
Cyclic String Rotation	Time Complexity: O(n²) Space Complexity: O(1)
Direct Character Mapping	Time Complexity: O(n) Space Complexity: O(1)

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.

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).

String Transformation solution and explanation

The problem

Approach overview

Approach 1: Cyclic String Rotation

Approach 2: Direct Character Mapping

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

String Transformation solution and explanation

The problem

Approach overview

Approach 1: Cyclic String Rotation

Approach 2: Direct Character Mapping

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems