Finding the Alphabetically Largest Letter in a String

Finding the Alphabetically Largest Letter in a String (Optimized Approach)

When solving problems related to string analysis, efficiency is key, especially when handling large inputs.

In this article, we will compare different implementations to find the alphabetically largest letter that appears in both uppercase and lowercase in a given string.

I will help you examine their time and space complexities and optimize the solution for the best performance.

Problem Statement

String S has uppercase & lowercase letters in English, and we need to return the largest letter (in uppercase) that appears in both forms. If no such letter exists, return "NO".

Example Scenarios

Example 1

Input: "aaBabcDaA"

Output: "B"

Example 2

Input: "Codility"

Output: "NO"

Example 3

Input: "WeTestCodErs"

Output: "T"

Initial Brute Force Approach

This initial approach checks every uppercase letter and verifies if its lowercase version exists in the string. However, checking membership in a string is an O(N) operation, making this inefficient.

# Brute force approach (O(N^2))
def largest_letter(s):

    max_val = -float("inf")

    max_str = ""

    for i in s: # O(N) - Iterates through the string once

        ord_val = ord(i) # O(1)

        if ord_val >= 97: # O(1) - Check if it's a lowercase letter

            continue

        if ord_val > max_val and i.lower() in s: # O(N) - Membership check in string

            max_val = ord_val

            max_str = i

    return max_str if len(max_str) > 0 else "NO" # O(1)

Time Complexity: O(N^2)

The nested check i.lower() in s runs in O(N), making the overall complexity O(N^2). It is inefficient for large inputs.

Space Complexity: O(1)

The solution only uses a few extra variables, making its space complexity constant.

Optimized Approach Using Sets

To improve efficiency, we can convert the string into a set. It allows O(1) lookups instead of O(N), reducing the overall time complexity to O(N).

# Optimized approach (O(N))
def largest_letter(s):

    max_val = -float("inf")
    max_str = ""

    s_set = set(s) # Convert string to a set for O(1) lookups

    for i in s: # O(N) iteration over the string

        ord_val = ord(i)

        if ord_val >= 97: # Ignore lowercase letters
            continue

        if ord_val > max_val and i.lower() in s_set: # O(1) lookup in set
            max_val = ord_val
            max_str = i

    return max_str if max_str else "NO"

Time Complexity: O(N)

• Creating the set: O(N)
• Iterating through the string: O(N)
• Lookups in the set: O(1)

Space Complexity: O(N)

The additional space used is for the set, which, in the worst case, stores all N characters.

Further Optimization Using Two Sets

Another optimized approach leverages two sets—one for lowercase letters and one for uppercase letters. It allows efficient lookups and ensures we find the largest valid letter in O(1) constant time after the initial scan.

class Solution:

    def solution(self, S: str)-> str:

        lower_set = set()
        upper_set = set()


        for char in S: # O(N) - Iterates through the string once
            if char.islower():      # O(1) check
                lower_set.add(char) # O(1) insert
            else:
                upper_set.add(char) # O(1) insert


        for char in range(90, 64, -1): # O(26), (constant time)
            upper_char = chr(char)
            lower_char = chr(char + 32)

            
            if upper_char in upper_set and lower_char in lower_set: # O(1) lookups
                return upper_char # O(1)

        return "NO" # O(1)

Time Complexity: O(N)

It is optimal since we:

• Scan the string once (O(N)) to populate sets.
• Perform at most 26 iterations (O(1)) over uppercase letters.

Space Complexity: O(1)

Since the sets only store alphabetic characters (maximum of 52 letters), this is considered O(1) extra space.

Comparing All Approaches

Approach                                      Time Complexity                                     Space Complexity                           Performance

Brute Force                                       O(N^2)                                                            O(1)                                             Slow

Set-Based Optimization                O(N)                                                                O(N)                                             Faster

Two-Set Method                              O(N)                                                                 O(1)                                             Optimal

The Best Approach

The two-set approach is the most efficient as it runs in O(N) time and O(1) space. It makes it ideal for handling large inputs.

Next Steps

Try running these solutions with large test cases to see the difference in execution speed.

If you work with big data or performance-critical applications, always aim for O(N) or better solutions whenever possible!

Need help with more optimization problems? Follow for more insights into writing efficient code!