<p>Given an array <code>arr</code> of 4 digits, find the latest 24-hour time that can be made using each digit <strong>exactly once</strong>.</p>

<p>24-hour times are formatted as <code>&quot;HH:MM&quot;</code>, where <code>HH</code> is between <code>00</code> and <code>23</code>, and <code>MM</code> is between <code>00</code> and <code>59</code>. The earliest 24-hour time is <code>00:00</code>, and the latest is <code>23:59</code>.</p>

<p>Return <em>the latest 24-hour time in <code>&quot;HH:MM&quot;</code> format</em>. If no valid time can be made, return an empty string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,3,4]
<strong>Output:</strong> &quot;23:41&quot;
<strong>Explanation:</strong> The valid 24-hour times are &quot;12:34&quot;, &quot;12:43&quot;, &quot;13:24&quot;, &quot;13:42&quot;, &quot;14:23&quot;, &quot;14:32&quot;, &quot;21:34&quot;, &quot;21:43&quot;, &quot;23:14&quot;, and &quot;23:41&quot;. Of these times, &quot;23:41&quot; is the latest.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [5,5,5,5]
<strong>Output:</strong> &quot;&quot;
<strong>Explanation:</strong> There are no valid 24-hour times as &quot;55:55&quot; is not valid.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>arr.length == 4</code></li>
	<li><code>0 &lt;= arr[i] &lt;= 9</code></li>
</ul>

/*
https://github.com/dhrubajyotinath6/Preparation/blob/master/DSA/STRIVER/Striver%20sde%20sheet/permutationsCppApproach-2

https://leetcode.com/problems/largest-time-for-given-digits/solution/
*/

class Solution {

private:
    void buildTime(vector<int> &nums, int &maxi){
        
       int hour = nums[0] * 10 + nums[1];
       int minutes = nums[2] * 10 + nums[3];
        
       if(hour < 24 && minutes < 60){
            maxi = max(maxi, hour * 60 + minutes);
       }
    }
    
private: 
    void recurPermute(int index, vector<int> &nums, int &maxi) {
        
        if(index == nums.size()) {
            buildTime(nums, maxi);
            return; 
        }
        
        for(int i = index;i<nums.size();i++) {
            swap(nums[index], nums[i]); 
            recurPermute(index+1, nums, maxi); 
            swap(nums[index], nums[i]); 
        }
        
    }
    
private:
    void permute(vector<int>& nums, int &maxi) {
        recurPermute(0, nums, maxi);  
    }
   
/*
1. std::ostringstream allows us to build a string without needing a buffer.
2. std::setw(2) ensures that each part (hours and minutes) is printed with at least two digits.
3. std::setfill('0') makes sure the output is padded with zeros if necessary (e.g., 02 instead of 2).

eg: maxTime = 244, then ans = 04 : 04

244/60 = 4 --> 04
255 % 60 = 4 --> 04
*/
private:
    string formatTime(int maxTime) {
        
    ostringstream oss;
        
    oss << setw(2) << setfill('0') << maxTime / 60
        << ":"
        << setw(2) << setfill('0') << maxTime % 60;
        
    return oss.str();
}
    
public:
    string largestTimeFromDigits(vector<int>& arr) {
        
        
        int maxi = -1;
        
        permute(arr, maxi);
        
        if(maxi == -1){
            return "";
        }
        return formatTime(maxi);
    }
};

/*
TC - O(1)
SC - O(1)

*/
11200