Problem Link:
Difficulty:
Easy
Pre-requisites:
ad-hoc
Problem:
You are given a string of digits 0-9, and uppercase letters ‘A’-‘Z’. Given that you are allowed to modify atmost one letter to any digit, what is the largest number you can get as a contiguous substring of the modified string.
Quick Explanation:
Given the string S, lets say we choose to modify the letter S[i]. It will always be in our interest to make S[i] = 9. The reason is, if S[i] were modified to anything else, and if that digit was used in our final number, then it would be <= number formed by making S[i] = 9.
So take each letter, modify it to the number ‘9’, and check if you get a larger number than your currently formed best. This approach takes O(|S|^2) time and if implemented correctly, is good enough to pass.
At the same time, one catch was that since the number of digits can be pretty large, actually storing the number as an int / long long would not work. You would have to compare numbers as strings. Here, care should be taken that merely comparing lengths and then for the same length doing lexicographic comparison would fail for cases of comparison with a longer string have leading zeros.
High level pseudocode for the entire program:
string ans = findBest(S)
for each character c in S
if(c is a letter)
change c to 9
string cons = findBest(S)
if(compare(cons, and) gives cons larger)
ans = cons
output ans
(“detailed”) Pseudocode for the compare function:
rawcomplt(string A, string B):
if(A.length() < B.length())
return true;
else if(A.length() > B.length())
return false;
else return A < B;
compare(string A, string B)
int startA, startB
for(startA = 0; startA < A.length(); startA++)
if(A[startA] != '0')
break;
for(startB = 0; startB < B.length(); startB++)
if(B[startB] != '0')
break;
return rawcomplt(A.subtr(startA, A.length()), B.substr(startB, B.length()));
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
with the hint.