Given a string S consisting of N unique lowercase alphabets and an array arr[] of length N where character S[i] represents the bulb and arr[i] represents the time up to which the ith bulb glows, starting from the time arr[i – 1]. The task is to find the bulb with maximum glowing time. If there exists more than one bulb with the same maximum glowing time, print the lexicographically greater one.
Examples:
Input: S = “abcd”, arr[] = {9, 29, 49, 50}
Output: c
Explanation:
‘c’ at index 0 has a duration = 9.
‘b’ at index 1 has a duration = arr[1] – arr[0] = 29 – 9 = 20
‘c’ at index 2 has a duration = arr[2] – arr[1]= 49 – 29 = 20
‘d’ at index 3 has a duration = arr[3] – arr[2]= 50 – 49 = 1
Two bulbs, ‘b’ and ‘c’, have the maximum glowing time. Among those two, ‘c’ is lexicographically larger.Input: S = “spuda”, arr[] = {12, 23, 36, 46, 62}
Output: a
Explanation:
‘s’ at index 0 has a duration = 12.
‘p’ at index 1 has a duration = arr[1] – arr[0] = 23-12 = 11.
‘u’ at index 2 has a duration = arr[2] – arr[1] = 36-23 = 13.
‘d’ at index 3 has a duration = arr[3] – arr[2] = 46-36 = 10.
‘a’ at index 4 has a duration = arr[4] – arr[3] = 62-46 = 16.
Therefore, ‘a’ has maximum glowing time.
Approach: The idea is to traverse the array and for each array element, calculate arr[i] – arr[i – 1]. Then, print the lexicographically larger bulb having maximum glowing time. Follow the steps below to solve the problem:
- Initialize two variables, say maxDur and maxPos, to store the glowing time and the index of the bulb with maximum glowing time, respectively.
- Traverse the given array and perform the following steps:
- If the current time (arr[i] – arr[i – 1]) is smaller than maxCurr, update maxCurr as maxCurr = arr[i] – arr[i – 1].
- Otherwise, if it is equal to maxCurr, maxPos does not contain any valid index and S[maxPos] is lexicographically smaller than S[i], update maxPos as maxPos = i.
- After completing the above steps, print S[maxPos] as the required output.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the bulb // having maximum glow char longestLastingBulb( vector< int > onTime, string s) { char ans; int n = onTime.size(); // Initialize variables int maxDur = INT_MIN; int maxPos = INT_MIN; int currentDiff = 0; // Traverse the array consisting // of glowing time of the bulbs for ( int i = 0; i < n; i++) { // For 1st bulb if (i == 0) { currentDiff = onTime[i]; maxDur = currentDiff; maxPos = i; } else { // Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1]; // Update the maximum glow if (maxDur < currentDiff) { maxDur = currentDiff; maxPos = i; } // Find lexicographically // largest bulb else { if (maxDur == currentDiff) { char one = s[i]; char two = s[maxPos]; if (one > two) { maxDur = currentDiff; maxPos = i; } } } } } // Bulb with maximum time ans = s[maxPos]; // Return the resultant bulb return ans; } // Driver Code int main() { string S = "spuda" ; vector< int > arr = { 12, 23, 36, 46, 62 }; // Function call cout << longestLastingBulb(arr, S); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the bulb // having maximum glow static char longestLastingBulb( int []onTime, char []s) { char ans; int n = onTime.length; // Initialize variables int maxDur = Integer.MIN_VALUE; int maxPos = Integer.MIN_VALUE; int currentDiff = 0 ; // Traverse the array consisting // of glowing time of the bulbs for ( int i = 0 ; i < n; i++) { // For 1st bulb if (i == 0 ) { currentDiff = onTime[i]; maxDur = currentDiff; maxPos = i; } else { // Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1 ]; // Update the maximum glow if (maxDur < currentDiff) { maxDur = currentDiff; maxPos = i; } // Find lexicographically // largest bulb else { if (maxDur == currentDiff) { char one = s[i]; char two = s[maxPos]; if (one > two) { maxDur = currentDiff; maxPos = i; } } } } } // Bulb with maximum time ans = s[maxPos]; // Return the resultant bulb return ans; } // Driver Code public static void main(String[] args) { String S = "spuda" ; int []arr = { 12 , 23 , 36 , 46 , 62 }; // Function call System.out.print(longestLastingBulb(arr, S.toCharArray())); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach import sys INT_MIN = (sys.maxsize - 1 ) # Function to find the bulb # having maximum glow def longestLastingBulb(onTime, s): n = len (onTime) # Initialize variables maxDur = INT_MIN maxPos = INT_MIN currentDiff = 0 # Traverse the array consisting # of glowing time of the bulbs for i in range (n): # For 1st bulb if (i = = 0 ): currentDiff = onTime[i] maxDur = currentDiff maxPos = i else : # Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1 ] # Update the maximum glow if (maxDur < currentDiff): maxDur = currentDiff maxPos = i # Find lexicographically # largest bulb else : if (maxDur = = currentDiff): one = s[i] two = s[maxPos] if (one > two): maxDur = currentDiff maxPos = i # Bulb with maximum time ans = s[maxPos] # Return the resultant bulb return ans # Driver Code if __name__ = = "__main__" : S = "spuda" arr = [ 12 , 23 , 36 , 46 , 62 ] # Function call print (longestLastingBulb(arr, S)) # This code is contributed by AnkThon |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the bulb // having maximum glow static char longestLastingBulb( List< int > onTime, string s) { char ans; int n = onTime.Count; // Initialize variables int maxDur = Int32.MinValue; int maxPos = Int32.MinValue; int currentDiff = 0; // Traverse the array consisting // of glowing time of the bulbs for ( int i = 0; i < n; i++) { // For 1st bulb if (i == 0) { currentDiff = onTime[i]; maxDur = currentDiff; maxPos = i; } else { // Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1]; // Update the maximum glow if (maxDur < currentDiff) { maxDur = currentDiff; maxPos = i; } // Find lexicographically // largest bulb else { if (maxDur == currentDiff) { char one = s[i]; char two = s[maxPos]; if (one > two) { maxDur = currentDiff; maxPos = i; } } } } } // Bulb with maximum time ans = s[maxPos]; // Return the resultant bulb return ans; } static void Main() { string S = "spuda" ; List< int > arr = new List< int >( new int [] {12, 23, 36, 46, 62}); // Function call Console.Write(longestLastingBulb(arr, S)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program for the above approach // Function to find the bulb // having maximum glow function longestLastingBulb(onTime, s) { let ans; let n = onTime.length; // Initialize variables let maxDur = Number.MIN_VALUE; let maxPos = Number.MIN_VALUE; let currentDiff = 0; // Traverse the array consisting // of glowing time of the bulbs for (let i = 0; i < n; i++) { // For 1st bulb if (i == 0) { currentDiff = onTime[i]; maxDur = currentDiff; maxPos = i; } else { // Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1]; // Update the maximum glow if (maxDur < currentDiff) { maxDur = currentDiff; maxPos = i; } // Find lexicographically // largest bulb else { if (maxDur == currentDiff) { let one = s[i]; let two = s[maxPos]; if (one > two) { maxDur = currentDiff; maxPos = i; } } } } } // Bulb with maximum time ans = s[maxPos]; // Return the resultant bulb return ans; } // Driver code let S = "spuda" ; let arr = [ 12, 23, 36, 46, 62 ]; // Function call document.write(longestLastingBulb(arr, S)); // This code is contributed by divyesh072019 </script> |
a
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach :
The given code identifies the bulb with the longest duration of lighting in a string S made up of distinct lowercase alphabets and an array arr of length N, where arr[i] denotes the duration of glowing for the ith bulb, counting backward from arr[i-1]. The method used by the code entails repeatedly iterating through the array arr to determine each bulb’s lighting time by deducting the glowing time of the preceding bulb. The code maintains track of the bulb connected to the longest duration yet discovered. The code changes the related bulb and the maximum duration if the current bulb’s duration exceeds the maximum duration. The function adjusts the maximum duration if the current bulb’s duration is equal to that value.
Approach :
- Create a dictionary to store the bulbs and their corresponding durations.
- Traverse the array arr[] from left to right.
- For each element, add the corresponding bulb and duration to the dictionary.
- After completing the traversal, iterate through the dictionary to find the bulb with the maximum duration.
- In case of a tie, compare the keys (bulb names) to determine the lexicographically greater bulb.
Below is the implementation of the above approach:
C++
// c++ code implementation for above approache #include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; char longestLastingBulb( const vector< int >& arr, const string& S) { int max_duration = 0; char max_bulb = S[0]; map< int , char > durations; for ( int i = 0; i < S.size(); i++) { int duration = arr[i] - (i > 0 ? arr[i-1] : 0); if (duration > max_duration) { max_duration = duration; max_bulb = S[i]; durations.clear(); durations[max_duration] = max_bulb; } else if (duration == max_duration) { durations[max_duration] = max(S[i], max_bulb); } } return durations[max_duration]; } int main() { string S = "spuda" ; vector< int > arr = { 12, 23, 36, 46, 62 }; // Function call char result = longestLastingBulb(arr, S); // Output the result cout << result << endl; return 0; } |
C#
// C# code implementation for above approache using System; using System.Collections.Generic; class GFG { static char LongestLastingBulb(List< int > arr, string S) { int maxDuration = 0; char maxBulb = S[0]; Dictionary< int , char > durations = new Dictionary< int , char >(); for ( int i = 0; i < S.Length; i++) { int duration = arr[i] - (i > 0 ? arr[i - 1] : 0); if (duration > maxDuration) { maxDuration = duration; maxBulb = S[i]; durations.Clear(); durations[maxDuration] = maxBulb; } else if (duration == maxDuration) { durations[maxDuration] = ( char )Math.Max(S[i], maxBulb); } } return durations[maxDuration]; } static void Main() { string S = "spuda" ; List< int > arr = new List< int >{ 12, 23, 36, 46, 62 }; // Function call char result = LongestLastingBulb(arr, S); // Output the result Console.WriteLine(result); } } |
a
Time complexity : O(NlogN)
Auxilitary Space Complexity : O(N).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!