A couple of boundary cases where people failed:
(1) Bad comparison without allowing for leading zeroes (described in Editorial).
(2) Taking care of leading 0, but when the final answer actually is “0”, outputting “”.
(3) Searching for a letter to change, but the string consisting only of digits.
If your code is getting WA, check with these cases first.
Let d[i] denote the maximum length of contiguous digits that end with with c[i].
And let s[i] denote the maximum length of contiguous characters, containing at most 1 uppercase letter, that end with c[i].
The trick is to update these values at each index i and store the index of i that leads to s[i] having a maximum value.
Now, how do we go about filling s[] and d[]? Clearly, there are two cases to be considered.
Case 1: c[i] is a digit
We increment d[i] only if there’s an existing sequence of digits. This allows us to avoid leading zeroes. On the other hand, if there’s no existing sequence of digits and c[i] is a non-zero digit, then we have a running sequence of digits whose length is 1.
At this point, the code looks like this:
if (d[i-1] is not equal to zero)
d[i] = d[i-1] + 1
else{
if (c[i] is not equal to ‘0’)
d[i] = 1
}
The exact same analogy applies to s[i].
Case 2: c[i] is not a digit. We assert that c[i] is an uppercase letter.
Here, since c[i] is an uppercase character, d[i] must be zero.
Also, at this point, we append c[i] to the existing maximum length of digits at index (i-1) i.e. d[i-1]. Hence s[i] = d[i-1] + 1.
The rest is cakewalk from here and I do hope the logic is clear up to this point. You should be able to read and understand the code now
For The Above Input String, I checked the answers from two of the submissions and they gave 5556786881505146955221
But My Solution gave 7028544864737656560892
Getting WA … have checked for all the corner cases and getting correct result. Help me in figuring out what is it that I am doing wrong… need help with the test cases…