STRCOMPARE - Editorial

editorial
, ,
21

Consider this input.

Input

3
4
tjsa
zjhr
6
zuyesd
freogk
3
hhv
oqw

Expected Output

2
2
3

Your Output

3
2
3
22

We need to find the first index where a[i] != b[i], so we can simply maintain an array ‘eq[n]’ where eq[i] = number of elements from index i where a[i] = b[i].
Time complexity: O(n)

void solve() {
  int n;
  cin >> n;
  string a, b;
  cin >> a >> b;

  vi eq(n);
  int c = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (a[i] == b[i]) c++;
    else c = 0;
    eq[i] = c;
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    int j = i;
    bool ok = 0;
    while (j < n) {
      if (a[j] ^ b[j]) {
        ok = a[j] < b[j];
        break;
      }
      j += eq[j];
    }
    ans += ok;
  }
  cout << ans << '\n';
}
23

I took a lot of time to figure out but i came up with a simplest solution.You can use the Kadane’s algorithm,
here is my solution
https://www.codechef.com/viewsolution/56140040