Given a string str, the task is to find the maximum valued alphabet in str. The value of a particular alphabet is defined as the difference in the indices of its last and the first occurrence. If there are multiple such alphabets then find the lexicographically smallest alphabet.
Examples:
Input: str = “abbba”
Output: a
value(‘a’) = 4 – 0 = 4
value(‘b’) = 3 – 1 = 2Input: str = “bbb”
Output: b
Approach: The idea is to store the first and the last occurrences of each of the alphabets in two auxiliary arrays say first[] and last[]. Now, these two arrays can be used to find the maximum valued alphabet in the given string.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MAX = 26;// Function to return the maximum// valued alphabetchar maxAlpha(string str, int len){ // To store the first and the last // occurrence of all the characters int first[MAX], last[MAX]; // Set the first and the last occurrence // of all the characters to -1 for (int i = 0; i < MAX; i++) { first[i] = -1; last[i] = -1; } // Update the occurrences of the characters for (int i = 0; i < len; i++) { int index = (str[i] - 'a'); // Only set the first occurrence if // it hasn't already been set if (first[index] == -1) first[index] = i; last[index] = i; } // To store the result int ans = -1, maxVal = -1; // For every alphabet for (int i = 0; i < MAX; i++) { // If current alphabet doesn't appear // in the given string if (first[i] == -1) continue; // If the current character has // the highest value so far if ((last[i] - first[i]) > maxVal) { maxVal = last[i] - first[i]; ans = i; } } return (char)(ans + 'a');}// Driver codeint main(){ string str = "abbba"; int len = str.length(); cout << maxAlpha(str, len); return 0;} |
Java
// Java implementation of the approachclass GFG{static int MAX = 26;// Function to return the maximum// valued alphabetstatic char maxAlpha(String str, int len){ // To store the first and the last // occurrence of all the characters int []first = new int[MAX]; int []last = new int[MAX]; // Set the first and the last occurrence // of all the characters to -1 for (int i = 0; i < MAX; i++) { first[i] = -1; last[i] = -1; } // Update the occurrences of the characters for (int i = 0; i < len; i++) { int index = (str.charAt(i) - 'a'); // Only set the first occurrence if // it hasn't already been set if (first[index] == -1) first[index] = i; last[index] = i; } // To store the result int ans = -1, maxVal = -1; // For every alphabet for (int i = 0; i < MAX; i++) { // If current alphabet doesn't appear // in the given String if (first[i] == -1) continue; // If the current character has // the highest value so far if ((last[i] - first[i]) > maxVal) { maxVal = last[i] - first[i]; ans = i; } } return (char)(ans + 'a');}// Driver codepublic static void main(String[] args){ String str = "abbba"; int len = str.length(); System.out.print(maxAlpha(str, len));}}// This code is contributed by 29AjayKumar |
Python
# Python implementation of the approachMAX = 26# Function to return the maximum# valued alphabetdef maxAlpha(str, len): # To store the first and the last # occurrence of all the characters # Set the first and the last occurrence # of all the characters to -1 first = [-1 for x in range(MAX)] last = [-1 for x in range(MAX)] # Update the occurrences of the characters for i in range(0,len): index = ord(str[i])-97 # Only set the first occurrence if # it hasn't already been set if (first[index] == -1): first[index] = i last[index] = i # To store the result ans = -1 maxVal = -1 # For every alphabet for i in range(0,MAX): # If current alphabet doesn't appear # in the given string if (first[i] == -1): continue # If the current character has # the highest value so far if ((last[i] - first[i]) > maxVal): maxVal = last[i] - first[i]; ans = i return chr(ans + 97)# Driver codestr = "abbba"len = len(str)print(maxAlpha(str, len))# This code is contributed by Sanjit_Prasad |
C#
// C# implementation of the approachusing System;class GFG{static int MAX = 26;// Function to return the maximum// valued alphabetstatic char maxAlpha(String str, int len){ // To store the first and the last // occurrence of all the characters int []first = new int[MAX]; int []last = new int[MAX]; // Set the first and the last occurrence // of all the characters to -1 for (int i = 0; i < MAX; i++) { first[i] = -1; last[i] = -1; } // Update the occurrences of the characters for (int i = 0; i < len; i++) { int index = (str[i] - 'a'); // Only set the first occurrence if // it hasn't already been set if (first[index] == -1) first[index] = i; last[index] = i; } // To store the result int ans = -1, maxVal = -1; // For every alphabet for (int i = 0; i < MAX; i++) { // If current alphabet doesn't appear // in the given String if (first[i] == -1) continue; // If the current character has // the highest value so far if ((last[i] - first[i]) > maxVal) { maxVal = last[i] - first[i]; ans = i; } } return (char)(ans + 'a');}// Driver codepublic static void Main(String[] args){ String str = "abbba"; int len = str.Length; Console.Write(maxAlpha(str, len));}}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of the approach const MAX = 26; // Function to return the maximum // valued alphabet function maxAlpha(str, len) { // To store the first and the last // occurrence of all the characters var first = new Array(MAX); var last = new Array(MAX); // Set the first and the last occurrence // of all the characters to -1 for (var i = 0; i < MAX; i++) { first[i] = -1; last[i] = -1; } // Update the occurrences of the characters for (var i = 0; i < len; i++) { var index = str[i].charCodeAt(0) - "a".charCodeAt(0); // Only set the first occurrence if // it hasn't already been set if (first[index] === -1) first[index] = i; last[index] = i; } // To store the result var ans = -1, maxVal = -1; // For every alphabet for (var i = 0; i < MAX; i++) { // If current alphabet doesn't appear // in the given String if (first[i] === -1) continue; // If the current character has // the highest value so far if (last[i] - first[i] > maxVal) { maxVal = last[i] - first[i]; ans = i; } } return String.fromCharCode(ans + "a".charCodeAt(0)); } // Driver code var str = "abbba"; var len = str.length; document.write(maxAlpha(str, len)); </script> |
Output:
a
Time Complexity: O(N)
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
