Leetcode 466 Solution

This article provides solution to leetcode question 466 (count-the-repetitions)
Categories:
Tags:
Access this page by simply typing in "lcs 466" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/count-the-repetitions

Solution

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int cnt = 0;
        int j = 0;
        unordered_map<int, pair<int, int>> next;

        for (int t = 0; t < n1; t++)
        {
            if (next.find(j) == next.end())
                next[j] = make_pair(t, cnt);
            else
            {
                auto last_pair = next[j];
                int sec_num = t - last_pair.first;
                int sec_cnt = cnt - last_pair.second;

                cnt += (n1 - t) / sec_num * sec_cnt;
                t = t + (n1 - t) / sec_num * sec_num;

                next.clear();
                continue;
            }

            for (int i = 0; i < s1.size(); i++)
            {
                if (s1[i] == s2[j])
                    j++;

                if (j == s2.size())
                {
                    j = 0;
                    cnt++;
                }
            }
        }

        return cnt / n2;
    }
};