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
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. LCS Returns

LCS Returns

Problem
Submissions
Leaderboard
Discussions
Editorial

Given two strings, and , find and print the total number of ways to insert a character at any position in string such that the length of the Longest Common Subsequence of characters in the two strings increases by one.

Input Format

The first line contains a single string denoting .
The second line contains a single string denoting .

Constraints

Scoring

  • Strings and are alphanumeric (i.e., consisting of arabic digits and/or upper and lower case English letters).
  • The new character being inserted must also be alphanumeric (i.e., a digit or upper/lower case English letter).

Subtask

  • for of the maximum score.

Output Format

Print a single integer denoting the total number of ways to insert a character into string in such a way that the length of the longest common subsequence of and increases by one.

Sample Input

aa
baaa

Sample Output

4

Explanation

The longest common subsequence shared by and is aa, which has a length of . There are two ways that the length of the longest common subsequence can be increased to by adding a single character to :

  1. There are different positions in string where we could insert an additional a to create longest common subsequence aaa (i.e., at the beginning, middle, and end of the string).
  2. We can insert a b at the beginning of the string for a new longest common subsequence of baa.

As we have ways to insert an alphanumeric character into and increase the length of the longest common subsequence by one, we print on a new line.

Author

harshil7924

Difficulty

Medium

Max Score

50

Submitted By

3055

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Helpdesk
  • Careers
  • Terms Of Service
  • Privacy Policy

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website