Similar Problems
Similar Problems not available
Number Of Valid Clock Times  Leetcode Solution
LeetCode: Number Of Valid Clock Times Leetcode Solution
Difficulty: Easy
Topics: string
Problem Description:
Given a string of 4 digits, representing a time in the format "HH:MM", find all the valid time that can be formed by rearranging the digits.
A valid time is a time that satisfies the following criteria:
 The hour part must be between 00 and 23 (inclusive).
 The minute part must be between 00 and 59 (inclusive).
 Both the hour and minute parts must consist of at least two digits, and any leading zeroes must be omitted.
Example Input: "19:38"
Example Output: ["19:38", "19:83", "38:19", "38:91", "81:39", "81:93", "91:38", "91:83"]
Solution:
This problem asks us to find all the valid times that can be formed by rearranging the given input string. To approach this problem, we will need to break it down into smaller subproblems. Let's see how we can do this:

We need to extract the digits from the given input string and store them in an array. We can do this by iterating over the string and converting each character to an integer.

Once we have extracted the digits, we need to generate all the possible permutations of these digits. We can use recursion to achieve this. At each step, we will choose one digit from the array and add it to the current permutation. We will then remove this digit from the array and call the recursive function on the remaining digits. We will continue this process until we have added all the digits to the current permutation.

For each valid permutation, we need to check if it represents a valid time. To do this, we will need to extract the hour and minute parts from the permutation and check if they are within the valid range.

If a permutation represents a valid time, we will add it to our output array.
Here is the Python code to implement the above approach:
class Solution:
def __init__(self):
self.output = []
def permutation_helper(self, digits, current):
if len(digits) == 0:
self.output.append(current)
else:
for i in range(len(digits)):
remaining_digits = digits[:i] + digits[i+1:]
self.permutation_helper(remaining_digits, current + str(digits[i]))
def isValidTime(self, time):
hour = int(time[:2])
minute = int(time[2:])
return 0 <= hour <= 23 and 0 <= minute <= 59
def permute(self, digits: str) > List[str]:
digits_array = [int(d) for d in digits]
self.permutation_helper(digits_array, "")
valid_times = []
for time in self.output:
if self.isValidTime(time):
valid_times.append(time[:2] + ":" + time[2:])
return valid_times
In this code, we define a class Solution
that contains the three helper functions we discussed above: permutation_helper
, isValidTime
, and permute
.
The permutation_helper
function generates all the possible permutations of the digits using recursion. It takes in two parameters: digits
(which is the remaining digits to be added to the current permutation) and current
(which is the current permutation being generated).
The isValidTime
function checks if a permutation represents a valid time by extracting the hour and minute parts and checking if they are within the valid range.
The permute
function is the main function that calls the permutation_helper
function and checks if each permutation is a valid time. It returns a list of all the valid times.
Number Of Valid Clock Times Solution Code
1