algoadvance

You are given a string s. A substring of s is called nice if it contains both lowercase and uppercase characters for every letter that appears in the substring. For example, “Bb” is a nice substring, but “BbA” is not because there’s no lowercase “a”. Return the longest nice substring of s. If there are multiple longest nice substrings, return any of them. If there are none, return an empty string.

Clarifying Questions

1. Are all input strings guaranteed to be non-empty?
   • Yes, the input string s is guaranteed to be non-empty.
2. What is the maximum length of the input string s?
   • The maximum length of the input string s is 100.
3. In case of ties (multiple substrings of the same maximum length), can we return any of them?
   • Yes, if there are multiple substrings of the same maximum length, returning any one of them is acceptable.

Strategy

To find the longest nice substring:

1. We can use a recursive approach to break the problem into smaller parts:
   • If the string s is nice, then return s.
   • If not, find a character that breaks the “nice” condition and split the string at that character.
   • Recursively apply the same process to each substring resulting from the split.
   • Return the longest nice substring found from these substrings.
2. For each string segment:
   • Check if it satisfies the “nice” condition (every character must appear in both uppercase and lowercase).
   • Recursively evaluate substrings when the condition is not met.

Code

def longestNiceSubstring(s: str) -> str:
    def is_nice(sub: str) -> bool:
        char_set = set(sub)
        for ch in char_set:
            if ch.swapcase() not in char_set:
                return False
        return True
    
    def helper(sub: str) -> str:
        if is_nice(sub):
            return sub
        max_len_nice_sub = ""
        for i in range(len(sub)):
            if not is_nice(sub[:i+1]):
                continue
            left_result = helper(sub[:i])
            right_result = helper(sub[i+1:])
            if len(left_result) > len(max_len_nice_sub):
                max_len_nice_sub = left_result
            if len(right_result) > len(max_len_nice_sub):
                max_len_nice_sub = right_result
        return max_len_nice_sub
    
    longest_nice_substring = helper(s)
    return longest_nice_substring

# Example usage:
s = "YazaAay"
print(longestNiceSubstring(s))  # Output could be "aAa" or "Aa"

Time Complexity

Let’s analyze the time complexity:

• The function is_nice has a time complexity of O(N) in the worst-case scenario, where N is the length of the string.
• The worst-case scenario of the recursive helper function involves splitting the string in all possible ways, leading to a recursive depth and breadth both approximately equal to the length of s, meaning it leads to an exponential time complexity.

Overall, the time complexity can be approximated as O(N * 2^N) in the worst case, making this a relatively high computational approach. However, given the constraint of string length up to 100, this method can be practical.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?