First time using rolling hash to AC a problem

Jimmy (xiaoke) Shen
3 min readFeb 8, 2024

--

Minimum Time to Revert Word to Initial State II — LeetCode Contest

This is a LC contest problem. If you participate in this contest, you may know that interesting python O(n²) solution can get AC. Then after the contest, the LC team update the test case, meanwhile, change the constraints of the question from

1 <= word.length <= 10^5

to

1 <= word.length <= 10^6

Then my submission failed, not because of the time complexity too high, but because the static size vector out of boundary.

Specifically the 3rd line:

const int MAX_N = 100010;

should be changed to following to make it work

const int MAX_N = 1000010;

Although, it is not professional to change the constraints, seems we don’t need complain as they provide free contest?

Minimum Time to Revert Word to Initial State II — LeetCode Contest

Here is a solution of using rolling hash to solve this problem.


typedef long long ll;
typedef vector<int> vi;
const int MAX_N = 1000010;
const int p = 131; // p and M are
const int M = 1e9+7; // relatively prime

int Pow[MAX_N];

vi computeRollingHash(string &T) { // Overall: O(n)
//vi Pow(MAX_N,0);
vi h(MAX_N, 0);
const int n = T.size();
Pow[0] = 1; // compute p^i % M
for (int i = 1; i < n; ++i) // O(n)
Pow[i] = ((ll)Pow[i-1]*p) % M;
h[0] = 0;
for (int i = 0; i < n; ++i) { // O(n)
if (i != 0) h[i] = h[i-1]; // rolling hash
h[i] = (h[i] + ((ll)T[i]*Pow[i]) % M) % M;
}
return h;
}

int extEuclid(int a, int b, int &x, int &y) { // pass x and y by ref
int xx = y = 0;
int yy = x = 1;
while (b) { // repeats until b == 0
int q = a/b;
tie(a, b) = tuple(b, a%b);
tie(x, xx) = tuple(xx, x-q*xx);
tie(y, yy) = tuple(yy, y-q*yy);
}
return a; // returns gcd(a, b)
}

int modInverse(int b, int m) { // returns b^(-1) (mod m)
int x, y;
int d = extEuclid(b, m, x, y); // to get b*x + m*y == d
if (d != 1) return -1; // to indicate failure
// b*x + m*y == 1, now apply (mod m) to get b*x == 1 (mod m)
return (x+m)%m; // this is the answer
}


int hash_fast(int L, int R, vi &h) { // O(1) hash of any substr
if (L == 0) return h[R]; // h is the prefix hashes
int ans = 0;
ans = ((h[R] - h[L-1]) % M + M) % M; // compute differences
ans = ((ll)ans * modInverse(Pow[L], M)) % M; // remove P[L]^-1 (mod M)
return ans;
}


class Solution {
public:
int minimumTimeToInitialState(string word, int k) {
vi h = computeRollingHash(word);
const int n = word.size();
if (n == k)return 1;
const int M = (n + k - 1) / k;
int left = 0;
int sz = 0;
for (int i = 1; i <= M; ++i){
left = i*k;
if (left >= n)return i;
sz = n - left;
// cout << i<<" "<<left << endl;
//cout << word.substr(left)<<endl;
int h1 = hash_fast(0, sz -1, h);
int h2 = hash_fast(left, n-1, h);
if (h1 == h2)return i;


}
return -1;

}
};

--

--