Longest Nice Substring

Easy

Asked by:

18 views

Topics:

StringsRecursion

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.

Example 2:

Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Example 3:

Input: s = "c"
Output: ""
Explanation: There are no nice substrings.

Constraints:

1 <= s.length <= 100
s consists of uppercase and lowercase English letters.

Try coding it in LeetCode

Longest Nice Substring

Easy

Asked by:

18 views

Topics:

StringsRecursion

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.

Example 2:

Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Example 3:

Input: s = "c"
Output: ""
Explanation: There are no nice substrings.

Constraints:

1 <= s.length <= 100
s consists of uppercase and lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the input string?
Is the definition of 'nice' case-sensitive? For example, if 'A' is present, must 'a' also be present, and vice versa?
If there are multiple longest nice substrings of the same length, should I return any one of them or is there a specific requirement for which one to return (e.g., the first occurrence)?
What should I return if the input string is empty or null?
Can the input string contain characters other than uppercase and lowercase English letters (e.g., numbers, symbols)?

Brute Force Solution

Approach

The brute force approach to finding the longest nice substring involves checking every possible substring within the main string. For each substring, we determine if it's 'nice' based on the given criteria. Finally, we keep track of the longest 'nice' substring we've found.

Here's how the algorithm would work step-by-step:

Start by considering all substrings of length one.
Then consider all substrings of length two, then length three, and so on, up to the length of the entire string.
For each substring we examine, check if it meets the 'nice' criteria. This likely involves ensuring that for every lowercase letter present, its uppercase version is also present, and vice-versa.
If a substring is 'nice', compare its length to the length of the longest 'nice' substring we've found so far.
If the current 'nice' substring is longer than the longest 'nice' substring we've previously found, update our record of the longest 'nice' substring.
After checking all possible substrings, the substring we have recorded as the longest 'nice' substring is the answer.

Code Implementation

def longest_nice_substring_brute_force(input_string):
    longest_nice_substring = ""

    for substring_length in range(1, len(input_string) + 1):
        for starting_index in range(len(input_string) - substring_length + 1):
            substring = input_string[starting_index:starting_index + substring_length]

            # Check if the current substring is "nice"
            if is_nice(substring):

                # Update the longest nice substring found so far
                if len(substring) > len(longest_nice_substring):
                    longest_nice_substring = substring

    return longest_nice_substring

def is_nice(substring):
    for character in substring:
        if 'a' <= character <= 'z':
            # Check if the uppercase version exists
            if character.upper() not in substring:
                return False

        elif 'A' <= character <= 'Z':
            # Check if the lowercase version exists
            if character.lower() not in substring:
                return False

    return True

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible substrings of the input string of length n. Generating all substrings requires two nested loops, resulting in O(n^2) operations. For each substring, we need to check if it is 'nice'. This 'nice' check involves examining each character in the substring, taking O(n) time in the worst case. Therefore, the overall time complexity is O(n^2) * O(n) = O(n^3).

Space Complexity

O(1) – The brute force approach, as described, primarily uses variables for iterating through substrings and tracking the longest nice substring found so far. Checking if a substring is 'nice' likely involves a constant amount of extra space, such as a fixed-size set or boolean array, to keep track of which characters are present. Since the amount of extra space doesn't scale with the input string's length (N), but remains constant, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the longest substring where for every uppercase letter, its lowercase counterpart is also present, and vice-versa. The clever idea is to divide the problem into smaller, easier subproblems whenever we find a character that breaks the 'nice' condition.

Here's how the algorithm would work step-by-step:

If the input is short, it's automatically the answer.
Check if the whole string is 'nice'. If it is, we're done!
If the whole string isn't 'nice', find a character that causes it to fail (either its uppercase or lowercase version is missing).
Split the original string into substrings at every occurrence of that 'bad' character.
Now, check each of the smaller substrings independently to find the longest 'nice' substring.
From all the 'nice' substrings you find in the smaller pieces, pick the longest one. That's your answer!

Code Implementation

def longest_nice_substring(input_string):
    string_length = len(input_string)

    if string_length < 2:
        return input_string

    for index in range(string_length):
        character = input_string[index]
        if 'a' <= character <= 'z':
            if character.upper() not in input_string:
                break
        elif 'A' <= character <= 'Z':
            if character.lower() not in input_string:
                break
    else:
        return input_string

    longest_substring = ""
    # Split the string and recursively check each part.
    for substring in input_string.split(character):

        current_longest = longest_nice_substring(substring)
        if len(current_longest) > len(longest_substring):
            longest_substring = current_longest

    return longest_substring

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm works by recursively splitting the string at 'bad' characters. In the worst-case scenario, each split results in substrings that are only slightly smaller. Checking if a string is 'nice' involves iterating through it (O(n)). The recursive calls can potentially lead to checking nearly all possible substrings, resulting in a quadratic number of such checks. Therefore, the overall time complexity becomes O(n^2), where n is the length of the input string.

Space Complexity

O(N) – The algorithm uses recursion, and in the worst-case scenario, where each 'bad' character splits the string into very small substrings, the depth of the recursion can be proportional to the length of the input string, N. Each recursive call requires storing a new stack frame, which contains local variables and the return address. Therefore, the auxiliary space complexity is O(N) due to the recursion depth. Temporary substrings are generated by string slicing which can also be O(N).

Edge Cases

Case	How to Handle
Empty string	Return an empty string immediately as there can be no substring.
String of length 1	Return an empty string, as a nice string must contain both upper and lower case versions of a character.
String with all uppercase or all lowercase characters	Return an empty string, as there are no characters with both case versions present.
String with non-alphabetic characters	The solution should either ignore these characters or consider them invalid, based on the problem constraints; we will assume the solution ignores them.
Very long string (close to maximum string length)	Ensure the algorithm has reasonable time complexity (e.g., avoid exponential solutions) and doesn't cause stack overflow if using recursion.
String with many overlapping nice substrings	The solution should correctly identify the longest one among potentially multiple valid substrings.
String where the longest nice substring starts at the beginning or end	The solution must not miss the substring if it is located at the extreme ends of the input string.
String with characters close to ASCII boundaries (e.g., 'A' or 'z')	Ensure the character case comparison handles edge character correctly without index out of bounds exception if using array of fixed size based on character values.