Given a string S, find the largest alphabetic character, whose both uppercase and lowercase character appear in string str. The uppercase character should be returned. If there is no such character, return -1.
Input: str = "scdbaBxC"
Both the uppercase and lowercase characters for letter C is present in the string and it is also the largest alphabetical character, hence our output is C.
Input: str = "abeCD"
Explanation: Although the largest character is e in the string but the uppercase version is not present hence the output is -1.
We have presented two approaches to find the two elements:• Naive Approach
The basic technique for solving the problem indicated above is to check for the presence of each character in the string for both uppercase and lowercase characters, that is, both 'a' and 'A' should be present in the string for letter A. If such a letter is present, the character will be kept track of and only updated if the current character is greater than the previously selected character. In the worst-case scenario, this approach takes O(n^2) time and can be further optimised.
We exploit the fact that the English alphabet has 26 characters to optimise the above method. We can keep track of both lowercase and uppercase characters by keeping an array of size 26. If the current character is present in both uppercase and lowercase letters, we shall mark true in both the arrays when iterating through the given string. We'll run a loop from 25 to 0 and verify if both arrays have 'true' marked in them after marking all characters existing in the corresponding array. If affirmative, we print the character's uppercase letter; otherwise, we return -1.
Time Complexity: O(n) where n is length of string.
Space Complexity: O(52)