Maximum Time

Easy
0/40
Average time to solve is 15m
profile
Contributed by
11 upvotes
Asked in company
Google inc

Problem statement

You are given a string that represents time in the format hh:mm. Some of the digits are blank (represented by ‘?’). Fill in ‘?’ such that the time represented by this string is the maximum possible. Maximum time: 23:59, minimum time: 00:00. You can assume that the input string is always valid.

For Example : 
If the given input string is 1?:?8.
We can replace the first ‘?’ with 9 and second with 5 to get the maximum time of 19:58.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
 The first line contains a single integer ‘T’ denoting the number of test cases Then each test case follows.
 The first line of each test case contains a string in the format of ‘hh:mm’.
Output Format : 
 For each test case print a string denoting the maximum possible time after replacing the ‘?’ marks with numbers..

Output for each test case will be printed in a separate line.
Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints : 
1 <= T <= 1000     
|S| = 5

Time limit: 1 sec
Sample Input 1 :
2
?4:5?
23:5?
Sample Output 1 :
14:59
23:59
Explanation Of Sample Output 1 :
For test case 1 :
We can only put 0 and 1 at the first position. so we choose 1 for maximum time. We put 9 at the end to maximize the minutes.

For test case 2 :
23:59 is the maximum time possible for any string.
Sample Input 2 :
1
12:22
Sample Output 2 :
 12:22
Hint

Try to form cases for each position separately.

Approaches (1)
Observation

Let’s try to build the string character by character from left to right.

  • If the 0th character is ‘?’
    • If the next character can be less than 3 or ‘?’ we can place a ‘2’ here.
    • Else we are bound to place a ‘1’.
  • If the first character is ‘?’,
    • If the 0th character is less than ‘2’ we can place the character ‘9’.
    • Else we place the character ‘3’.
  • If the third character is ‘?’,
    • We place a ‘5’ here.
  • If the last character is ‘?’,
    • We place a ‘9’ here.
Time Complexity

O( 1 )

 

Since we are only checking for a constant number of positions. Hence the time complexity is O(1).

Space Complexity

O(1)

 

Since constant space is used. Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Maximum Time
Full screen
Console