We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Substring Diff
  5. Discussions

Substring Diff

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • 1998suraj
    5 years ago+ 3 comments

    Accepted solution in C++ Reference :Quora

    #include <bits/stdc++.h>
    using namespace std;
    int c[1505][1505];
    int l,s;
    bool solve(int mid)
    {
    	for(int i = mid;i <= l;i++)
        {
                for(int j = mid;j <= l;j++)
                {
                    int tmp = c[i][j] - c[i-mid][j-mid];
                    if(tmp <= s) return true;
                }
         }
            return false;
    }
    int main()
    {
    	int t;  cin>>t;
    	while(t--)
    	{
    		cin>>s;
    		string a,b;  cin>>a>>b;
    		  l = a.length();
    		  for(int i=0;i<l;++i)
    		  {
    		  	  for(int j=0;j<l;++j)
    		  	  {
    		  	  	if(a[i]==b[j])
    		  	  	 c[i+1][j+1] = c[i][j] ;
    		  	  	 else
    		  	  	 c[i+1][j+1] = c[i][j] +1;
    			  }
    		  }
    		  int low = 0,high = l,mid;
                while(low < high)
    			{
                    mid = (low + high + 1) >> 1;
                    if(solve(mid)) low = mid;
                    else high = mid - 1;
                }
    		  cout<<low<<endl;
    	}
    }
    
    6|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature