C++ solution


  • 0
    S
    class Solution {
    public:
        int getMaxRepetitions(string s1, int n1, string s2, int n2) {
            if (!s1.length() || !s2.length())  return 0;
            int a[s2.length()]{};
            int b[s2.length() + 1];
            b[0] = 0;
            int j = 0, m = 0, k;
            for (k = 1; k <= n1; ++k) {
                for (auto i : s1)  {
                    if (i == s2[j]) ++j;
                    if (j == s2.length()) {
                        ++m;
                        j = 0;
                    }
                }
                b[k] = m;
                if (!j || a[j]) break;
                a[j] = k;
            }
            if (n1 == k)  return b[n1] / n2;
            n1 -= a[j];
            return (n1 / (k - a[j]) * (b[k] - b[a[j]]) + b[a[j]] + b[n1 % (k - a[j]) + a[j]) / n2;
        }
    };
    

  • 0
    W

    Would you please explain the idea behind the code? thx


  • 0
    S

    U can imagine the problem as a “division”.
    a[j] is the non-repetitive part.
    (a[j] to k) is repetitive part.
    So u can calculate how many s2 can n1 * s1 obtain.
    It divided by n2 is the result.


  • 0
    7

    Error:

    s1="ecbafedcba";
    n1=6;
    s2="abcdef";
    n2=1;
    

    I have a similar solution.
    As we have discussed there, the last formula should change a little.

    return (n1 / (k - a[j]) * (b[k] - b[a[j]]) + b[n1 % (k - a[j]) + a[j]]) / n2;
    

  • 0
    S

    @70664914 yes, u r right. I forget the addition but it pass the test. So i have no check.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.