We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

String Transformation

Number: 3024

Difficulty: Hard

Paid? No

Companies: Snowflake, MathWorks, Atlassian, Google

Problem Description

Given two strings s and t of equal length n, you are allowed to perform an operation on s where you remove a proper non‐empty suffix (i.e. a suffix of length l with 0 < l < n) and then append it at the front of s. You are also given an integer k. The task is to count the number of ways to transform s into t in exactly k operations. (Since the answer can be huge, return it modulo 10^9 + 7.)

Key Insights

  • Each operation is equivalent to a rotation: removing a suffix of length l and attaching it to the front results in a right rotation by l positions.
  • The allowed “move” values are l ∈ {1, 2, …, n – 1}. In each operation, you add a rotation (modulo n).
  • Since rotations form a cyclic group (mod n), the overall transformation after k operations is the sum (mod n) of the individual rotations.
  • Use discrete Fourier analysis (or eigenvalue techniques for circulant matrices) on the polynomial F(x)= x^1 + x^2 + … + x^(n–1). Evaluating F(x) at n-th roots of unity shows that for j = 0, F(1) = n–1, and for j ≠ 0, F(ω^j) = –1.
  • Let N(r) be the number of sequences (of k moves) that result in a net rotation r mod n. Then:
    • For r = 0: N(0) = 1/n · [ (n–1)^k + (n–1)·(–1)^k ]
    • For r ≠ 0: N(r) = 1/n · [ (n–1)^k – (–1)^k ]
  • The string t is a rotation of s. Determine all d (0 ≤ d < n) such that if you rotate s to the right by d positions you get t. Let R be the set of such d.
  • Notice that although each move must be nonzero, a sequence of moves can sum (mod n) to 0. Therefore, even if 0 ∈ R (i.e. t equals s), the solution might be obtained through a combination of nonzero moves whose total rotation is 0.
  • Finally, if we let cnt0 = 1 if 0 ∈ R and let cnt_non0 = |R| – cnt0, then:
    • If 0 ∈ R, answer = N(0) + cnt_non0 · N(r)
    • Otherwise, answer = |R| · N(r)

Space and Time Complexity

Time Complexity: O(n) – mainly due to finding rotations using string matching (e.g. via KMP on s+s). Space Complexity: O(n) – for storing the concatenated string and any auxiliary arrays.

Solution

We first observe that the operation is equivalent to “rotating” the string. In one move, if you remove a suffix of length l (with 1 ≤ l ≤ n–1) and put it in the front, the string becomes a right rotation by l positions. Thus, the net effect of k operations is to add up k such moves, each chosen from {1, 2, …, n–1} (mod n).

Using generating functions, define F(x) = x + x^2 + … + x^(n–1). Then the number of ways to obtain a total (right) rotation of r mod n after k moves is the coefficient of x^r in (F(x))^k modulo (x^n – 1). By applying the discrete Fourier transform (DFT) over the cyclic group Z/nZ, we evaluate F(x) at the n-th roots of unity. One finds:

  • At ω^0 (i.e. 1), F(1) = n–1.
  • For ω^j with j ≠ 0, because 1 + ω^j + ω^(2j) + … + ω^((n–1)j) = –1, we have F(ω^j) = –1. Thus,   N(0) = 1/n · [ (n–1)^k + (n–1)·(–1)^k ] and for any nonzero rotation r,   N(r) = 1/n · [ (n–1)^k – (–1)^k ].

Now, we must determine for which rotations d (0 ≤ d < n) the string t can be obtained from s by a right rotation of d. This can be done by checking (efficiently using a string matching algorithm) the rotation equivalence between s and t.

Let |R| be the number of valid rotations with:   cnt0 = 1 if 0 ∈ R (i.e. if s equals t)   cnt_non0 = |R| – cnt0. Then the final answer is computed as:   If 0 ∈ R:    answer = N(0) + cnt_non0 · N(r)   Else:    answer = |R| · N(r) All computations are done modulo 10^9 + 7; note that division by n is performed via modular inverse.

Code Solutions

MOD = 10**9 + 7

# Fast modular exponentiation
def mod_exp(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp //= 2
    return result

# Extended Euclidean algorithm for modular inverse
def mod_inv(a, mod):
    return mod_exp(a, mod - 2, mod)

# KMP algorithm: find all starting indices where pattern p occurs in text t.
def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    lps = [0] * m
    # Preprocess lps array
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    # Search for pattern
    indices = []
    i = j = 0
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            indices.append(i - j)
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return indices

def count_transformations(s, t, k):
    n = len(s)
    # Find all rotations d (0 <= d < n) such that right rotation of s by d equals t.
    # One trick: t must appear in s+s at an index that is in [0, n).
    doubled = s + s
    # Get all occurrences (using KMP) of t in doubled. They correspond to left rotations.
    # However note: right rotation by d is equivalent to left rotation by n-d.
    occ = kmp_search(doubled, t)
    valid_rotations = set()
    for pos in occ:
        if pos < n:  # valid rotation index for left rotation
            # Convert left rotation pos into right rotation:
            # left rotation by pos: string becomes s[pos:] + s[:pos]
            # right rotation needed = n - pos  (mod n)
            d = (n - pos) % n
            valid_rotations.add(d)
    # Only consider rotations in 0..n-1.
    # Let R = valid_rotations. They are the rotations (by a right shift) that transform s into t.
    cntR = len(valid_rotations)
    if cntR == 0:
        return 0

    # Precompute (n-1)^k and (-1)^k modulo MOD
    r_pow = mod_exp(n - 1, k, MOD)
    minus_pow = mod_exp(MOD - 1, k, MOD)  # (-1)^k mod MOD
    
    inv_n = mod_inv(n, MOD)
    
    total = 0
    if 0 in valid_rotations:
        # There is one valid rotation = 0.
        ways0 = (r_pow + (n - 1) * minus_pow) % MOD
        # Every nonzero valid rotation:
        ways_non0 = (r_pow - minus_pow) % MOD
        # There are (cntR - 1) nonzero rotations since 0 is included.
        total = (ways0 + (cntR - 1) * ways_non0) % MOD
    else:
        # All valid rotations are nonzero.
        ways_non0 = (r_pow - minus_pow) % MOD
        total = (cntR * ways_non0) % MOD

    # Multiply by modular inverse of n (i.e. divide by n)
    total = (total * inv_n) % MOD
    return total

# Example usage:
s1 = "abcd"
t1 = "cdab"
k1 = 2
print(count_transformations(s1, t1, k1))  # Expected output: 2

s2 = "ababab"
t2 = "ababab"
k2 = 1
print(count_transformations(s2, t2, k2))  # Expected output: 2
← Back to All Questions