FastPrep

Description

Solutions

Submission

Maximize the Lottery ID

🤘 INTERN

The newspaper HackerRankNews distributed lottery tickets to everyone, and the winning lottery ID is described in the paper denoted by winnerID.

In order to win the lottery, a customer having a lottery ID denoted by lotteryID needs to maximize the length of the longest common subsequence of the strings lotteryID and winnerID. To do so, the customer can perform up to k operations. In each operation, the customer can change any character in lotteryID either to its next or previous character.

Find the maximum possible length of the longest common subsequence after at most k such operations.

Note:

Operations can be performed only on lotteryID, not on winnerID.
The next character of a given character ch is the character that comes just after it in the alphabet. Similarly, the previous character is the character that comes just before it in the alphabet. For example, the next character of 'm' is 'n' and the previous is 'l'. For 'z' the next character is 'a' and for 'a' the previous character is 'z'.

Example 1:

Input:  lotteryID = "fpeIqanxyk", winnerID = "hackerrank", k = 6
Output: 7 
Explanation:
The original explanation is not completed, I add my own understanding in the end for your reference. And also Output = 7 is calculated by me, it may not be accurate. It is just here for your refernce. Once I find more source, I will modify it immediately.

One of the optimal ways to perform the operations is as follows:
 

        Select i = 0, convert lotteryID[0] to its next character, lotteryID = "gpeIqanxyk"
        Select i = 0, convert lotteryID[0] to its next character, lotteryID = "hpeIqanxyk"
        Select i = 2, convert lotteryID[2] to its previous character, lotteryID = "hpdIqanxyk"
        Select i = 2, convert lotteryID[2] to its previous character, lotteryID = "hpcIqanxyk"

The maximum possible length of the longest common subsequence after at most k operations is 7.

Constraints:

TO-DO