Longest Common Subsequence Again
Practice
3.8 (6 votes)
Dynamic programming
Algorithms
Medium
Dynamic programming
Problem
89% Success 2091 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given two strings S, P and two integers, \(K1\), \(K2\). You have to find the length of the longest common subsequence after performing at-most \(K1\) operations on string S and at-most \(K2\) operations on string P. In one operation, you can change a character of the string to any alphabet.

INPUT FORMAT :
First line contains a string, S .
Second line contains a string, P.
Third line contains two space separated integers, \(K1\) and \(K2\) .

OUTPUT FORMAT :-
Print the length of the longest common subsequence after performing at-most \(K1\) operations on string S and at-most \(K2\) operations on string P.

CONSTRAINTS :-

  • \(1 \le |S| \le 500\) where S denotes the length of the string S
  • \(1 \le |P| \le 500\) where P denotes the length of the string P
  • \(0 \le K1 \le 10\)
  • \(0 \le K2 \le 10\)

    • Please login to use the editor

    You need to be logged in to access the code editor

    Loading...

    Please wait while we load the editor

    Loading...
    Results
    Custom Input
    Run your code to see the output
    Submissions
    Please login to view your submissions
    Similar Problems
    1.Almost correct bracket sequence
    Points:30
    15 votes
    Tags:
    Applications of Dynamic ProgrammingAlgorithmsDynamic ProgrammingDynamic programming
    2.ResourceTangle
    Points:30
    6 votes
    Tags:
    Applications of Dynamic ProgrammingAlgorithmsDynamic Programming
    3.Football teams
    Points:30
    2 votes
    Tags:
    Binary search algorithmDynamic ProgrammingMediumAlgorithmsDepth-first searchDynamic programmingDisjoint set