String Question

You are given a string A representing a number. The digits of the number only consists of digits 1 to 9.

You are given a function F that contains a mapping for digits from 1 to 9 i.e. F[i] transforms the digit i to the value defined in F[i].

You can apply the following operation at-most 1 time:

• Choose a continuous segment of digits in A and replace each digit x in this segment with a digit replaced using the function F.

What is the maximum number you can obtain in this manner? Since the number can be large, output it modulo 10^9 + 7

Input Format

The first line contains a string, A, denoting the number.

Each line i of the 9 subsequent lines (where 0 <=i<9) contains an integer describing F[i]

Can anyone tell what would be the correct solution/approach for this problem?

1 Like

U can solve it using sliding window technique or two pointer technique and just keep doing modulo and precalculate sum of each prefix and suffix

I was trying to solve this question. But, it didn’t pass in Hackwithinfy today.

This question was easy and it even was available on gfg

1 Like

I think this method will not work in the above question because the length of the string was very high(10^5). We can 't take modulo at the end, we need to somehow calculate the modulo during the process of calculating the maximum possible number.

I also used the logic still passed only 1 subtask, might be some edge cases is there.

AC in one go
should I post the solution?

2 Likes

yeah sure

3 Likes

How to solve the first problem? Count consecutive triplets?

same… only 1 testcase passed… i sat there for an hour debugging, i even rewrote the code in python …but no luck… i guess some issue with the test perhaps… its not possible otherwise or maybe i missed something who knows

1 Like

i had a different first problem…given an array choose 5 integers to maximize product

Yes, plzz share the approach of your solution

@king_of_string @yashdew @zero_bug
is the solution Maximize the given number by replacing a segment of digits with the alternate digits given - GeeksforGeeks correct or not? I think it is correct

Yes Please. I was also not able to do this. Only 1 TC passed

I had this. Greedy didn’t work. I got some thought of DP but could not implement it.

probably some problem with the testcases . I also mailed them about this. Now waiting for their reply. 