D
DevExCode

LeetCode 466: Count The Repetitions Solution

Master LeetCode problem 466 (Count The Repetitions), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

466. Count The Repetitions

Hard
StringDynamic Programming

Problem Explanation

Explanation:

To solve this problem, we need to find the maximum number of occurrences of s2 within s1 multiplied by n2, where s1 is repeated n1 times. We can achieve this by simulating the process of counting repetitions.

  1. Create a mapping to store the index of each character in s2.
  2. Initialize count1 and count2 to keep track of the current position in s1 and s2 respectively.
  3. Iterate over the characters in s1 n1 times:
    • Increment count1.
    • If the current character is equal to the character at index count2 in s2, increment count2.
    • If count2 reaches the end of s2, reset count2 to 0 and increment the number of repetitions.
  4. Return the maximum number of repetitions.

Time Complexity: O(n1 * s1.length() + n2 * s2.length()) Space Complexity: O(s2.length())

:

Solution Code

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int[] repeats = new int[s2.length() + 1];
        int[] nextIndex = new int[s2.length() + 1];
        
        int j = 0, count = 0;
        for (int k = 1; k <= n1; k++) {
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    j++;
                    if (j == s2.length()) {
                        j = 0;
                        count++;
                    }
                }
            }
            repeats[k] = count;
            nextIndex[k] = j;
            
            for (int start = 0; start < k; start++) {
                if (nextIndex[start] == j) {
                    int interval = k - start;
                    int repeatCount = (n1 - start) / interval;
                    int patternCount = (n1 - start) % interval + start;
                    return (repeats[start] + repeatCount * (repeats[k] - repeats[start])) / n2;
                }
            }
        }
        
        return repeats[n1] / n2;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 466 (Count The Repetitions)?

This page provides optimized solutions for LeetCode problem 466 (Count The Repetitions) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 466 (Count The Repetitions)?

The time complexity for LeetCode 466 (Count The Repetitions) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 466 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 466 in Java, C++, or Python.

Back to LeetCode Solutions