Largest Alphabetic Character

Problem Statement: Largest Alphabetic Character

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"
Output: C
Explanation:
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"
Output: -1
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.

Efficient Approach

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.

public class Main {

	public static String largestCharacter(String str)
	{
		boolean[] uppercase = new boolean[26];
		boolean[] lowercase = new boolean[26];

		char[] arr = str.toCharArray();

		for (char c : arr) {

			if (Character.isLowerCase(c))
				lowercase[c-'a'] = true;

			if (Character.isUpperCase(c))
				uppercase[c-'A'] = true;
		}

		for (int i = 25; i >= 0; i--) {

			if (uppercase[i] && lowercase[i])
				return (char)(i + 'A') + "";
		}

		return "-1";
	}

	public static void main(String[] args)
	{
		String str = "scdbaBxC";

		System.out.println(largestCharacter(str));
	}
}

def largestCharacter(str):
	
	uppercase = [False] * 26
	lowercase = [False] * 26
	
	arr = list(str)
	for c in arr:
		if (c.islower()):
			lowercase[ord(c) - ord('a')] = True
		if (c.isupper()):
			uppercase[ord(c) - ord('A')] = True
			
	for i in range(25,-1,-1):
		
		if (uppercase[i] and lowercase[i]):
			return chr(i + ord('A')) + ""
	return "-1"

str = "scdbaBxC"
print(largestCharacter(str))
	

Time Complexity: O(n) where n is length of string.

Space Complexity: O(52)