Modified String Transformation with Custom Rules

Modified String Transformation with Custom Rules

Problem Statement

You're given:

  • A string s consisting of lowercase English letters.

  • An integer t indicating the number of transformation steps.

  • An array nums of size 26 where nums[i] tells how many next consecutive characters to replace each letter 'a' + i with.

In each transformation:

  • For a character ch, it transforms into the next nums[ch - 'a'] characters in the alphabet.

  • If it goes past 'z', it wraps around from 'a'.

Your goal: Return the final length of the transformed string after t transformations. Since this can be large, return it modulo 10⁹ + 7.

Example

Input:

s = "abcyy", t = 2
nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]

Transformation:

  • Step 1 → "a" → "b", "b" → "c", ..., "y" → "z"
    → "bcdzz"

  • Step 2 → "b" → "c", "c" → "d", "d" → "e", "z" → "ab", "z" → "ab"
    → "cdeabab"

Output: 7

Best Data Structure for the Job

No fancy DS required here. A fixed-size frequency array of length 26 suffices. It helps track how many times each character appears and simulates transformations without reconstructing the full string.

Different Approaches

1. Brute Force (String Construction) — TLE Magnet

Rebuild the entire string at each transformation step. Very intuitive, but blows up for larger t.


public int bruteForceTransform(String s, int t, int[] nums) {
    final int MOD = 1_000_000_007;
    StringBuilder sb = new StringBuilder(s);

    while (t-- > 0) {
        StringBuilder next = new StringBuilder();
        for (char ch : sb.toString().toCharArray()) {
            int jump = nums[ch - 'a'];
            for (int i = 1; i <= jump; i++) {
                next.append((char) ('a' + (ch - 'a' + i) % 26));
            }
        }
        sb = next;
    }

    return sb.length() % MOD;
}

2. Frequency Simulation — Optimized for Moderate t

Track only how many of each character exist. Avoids actual string building.


public int simulateFrequencyTransform(String s, int t, int[] nums) {
    final int MOD = 1_000_000_007;
    long[] freq = new long[26];
    for (char ch : s.toCharArray()) freq[ch - 'a']++;

    while (t-- > 0) {
        long[] newFreq = new long[26];
        for (int i = 0; i < 26; i++) {
            long count = freq[i];
            for (int j = 1; j <= nums[i]; j++) {
                int nextChar = (i + j) % 26;
                newFreq[nextChar] = (newFreq[nextChar] + count) % MOD;
            }
        }
        freq = newFreq;
    }

    long total = 0;
    for (long val : freq) total = (total + val) % MOD;
    return (int) total;
}

3. Matrix Exponentiation — Optimized for Large t (Up to 10⁹)

This is where we flex that big-brain math. Each transformation is just matrix multiplication. Raise the transformation matrix to power t using fast exponentiation.


public int matrixTransform(String s, int t, List<Integer> nums) {
    final int MOD = 1_000_000_007;
    int[][] T = getTransformationMatrix(nums);
    int[][] T_pow = matrixPow(T, t);
    int[] count = new int[26];
    long[] resultFreq = new long[26];

    for (char c : s.toCharArray())
        count[c - 'a']++;

    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            resultFreq[j] = (resultFreq[j] + (long) count[i] * T_pow[i][j]) % MOD;
        }
    }

    long total = 0;
    for (long val : resultFreq) total = (total + val) % MOD;
    return (int) total;
}

private int[][] getTransformationMatrix(List<Integer> nums) {
    int[][] T = new int[26][26];
    for (int i = 0; i < 26; i++) {
        for (int j = 1; j <= nums.get(i); j++) {
            T[i][(i + j) % 26]++;
        }
    }
    return T;
}

private int[][] matrixPow(int[][] M, int n) {
    if (n == 0) return getIdentityMatrix(M.length);
    if (n % 2 == 1) return matrixMult(M, matrixPow(M, n - 1));
    return matrixPow(matrixMult(M, M), n / 2);
}

private int[][] matrixMult(int[][] A, int[][] B) {
    int sz = A.length;
    int[][] C = new int[sz][sz];
    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sz; j++) {
            for (int k = 0; k < sz; k++) {
                C[i][j] = (int)((C[i][j] + 1L * A[i][k] * B[k][j]) % MOD);
            }
        }
    }
    return C;
}

private int[][] getIdentityMatrix(int sz) {
    int[][] I = new int[sz][sz];
    for (int i = 0; i < sz; i++) I[i][i] = 1;
    return I;
}

⚠️ Common Pitfalls

  • Ignoring Wrap-around: Forgetting 'z' wraps back to 'a' will mess up your transformation.

  • Modular Arithmetic Issues: Not applying % MOD properly at every step causes overflow.

  • Trying to Store Full String: Leads to memory limits for large t.

📊 Complexity Recap

Approach    Time Complexity        Space Complexity
Brute Force    O(N × max(nums)^t)        High
Frequency Array Simulation    O(t × 26 × max(nums))        O(26)
Matrix Exponentiation (Optimized)    O(26³ × log t)        O(26²)

🌍 Real-World Use Cases

  • Text Generators & Morphing Algorithms: Rule-based pattern transformation engines.

  • Cryptographic Ciphers: Where deterministic transformation rules iterate over time.

  • DNA/RNA Simulation: Simulating generational transformations in genetic models.

  • Compression Predictions: Estimating growth or reduction in size due to repetitive transformations.


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Zero Array After Queries

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...
Read more