Why my logic is failing in certain test cases?

Question

I am solving this problem on codeforces : https://codeforces.com/contest/1492/problem/C

My code:

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    
      int n,m;
      cin>>n>>m;
      string str1,str2;
      cin>>str1;
      cin>>str2;
      
      int i=0;
      int p=0;
      vector<pair<int,int>>vec;
      while(i<n && p<m)
      {
          int j=i;
          int q=p;
          while(j<n-1 && str1[j+1]==str1[i])
          j++;
          while(q<m-1 && str2[q+1]==str2[p])
          q++;
          
          vec.push_back({i,i});
          vec.push_back({i+q-p,j});
          
          i=j+1;
          p=q+1;
      }
      int maxi=1;
      for(int i=0;i<vec.size()-1;i++)
      {
          maxi=max(maxi,vec[i+1].second-vec[i].first);
      }
    cout<<maxi<<endl;
    return 0;
}

My logic: For each character in t , I am finding the maximum and minimum valid indexes in s which are possible to be taken. Consider this example:

s-->"aaaabbbbbc"
t-->"aabc"

so my vector would be [(0,0) , (1,3) , (4,8) ,(9,9)]

However my code is failing in certain cases. Can someone point out the mistake?

Answer 1

Your code doesn't seem to be implementing your algorithm. In the loop you have

      vec.push_back({i,i});
      vec.push_back({i+q-p,j});

So the resulting vector would be alternating pairs of equal indexes and (potentially) different indexes. But:

[(0,0) , (1,3) , (4,8) ,(9,9)]

The (4, 8) pair can't be produced by {i, i}. Further the first pair in your example doesn't fit your stated algorithm either, the first a can be (0, 2).

Your code also seems to assume the letters in the strings are sorted. But what about this input?

s = "aaabbbaaabbbccc";
t = "abc";

You would only match a with the first triplet of as and b with the first triplet of bs and break down on the c completely.