How do you solve Longest Nice Substring on LeetCode?

Longest Nice Substring (LeetCode #1763) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: A substring is nice only if every character has both uppercase and lowercase forms present.

What is the brute force solution for Longest Nice Substring?

The brute force approach for Longest Nice Substring is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible substring of the input string to see if it is nice. This is straightforward but inefficient, as it requires examining many substrings. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Longest Nice Substring?

Clearly explain your thought process and the approach you are taking. Consider edge cases, such as strings with no nice substrings. Practice writing clean and efficient code, as clarity is key in interviews.

What are common mistakes when solving Longest Nice Substring?

Not checking all characters in the substring for both cases, leading to incorrect results. Failing to optimize the search process, resulting in unnecessary computations.

#1763

Longest Nice Substring

Easy

Hash TableStringDivide and ConquerBit ManipulationSliding WindowHash MapSliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a sliding window technique to efficiently find the longest nice substring. By maintaining a count of characters in a HashMap, we can quickly check if a substring is nice without needing to recheck every character repeatedly.

⚙️

Algorithm

6 steps

1Step 1: Initialize a HashMap to count occurrences of each character.
2Step 2: Use two pointers to represent the current window of the substring being examined.
3Step 3: Expand the right pointer to include new characters and update the HashMap.
4Step 4: Check if the current window is nice by verifying that all characters have both cases present.
5Step 5: If the current window is nice and longer than the previously found longest, update the longest substring.
6Step 6: If not nice, move the left pointer to shrink the window until it becomes nice again.

solution.py20 lines

1def longestNiceSubstring(s):
2    longest = ""
3    left = 0
4    count = {}
5    for right in range(len(s)):
6        count[s[right]] = count.get(s[right], 0) + 1
7        while not isNice(count):
8            count[s[left]] -= 1
9            if count[s[left]] == 0:
10                del count[s[left]]
11            left += 1
12        if isNice(count) and (right - left + 1) > len(longest):
13            longest = s[left:right + 1]
14    return longest
15
16def isNice(count):
17    for c in count:
18        if count[c.lower()] == 0 or count[c.upper()] == 0:
19            return False
20    return True

ℹ

Complexity note: The time complexity is O(n) because we only pass through the string a limited number of times. The space complexity is O(n) due to the HashMap storing character counts.

1A substring is nice only if every character has both uppercase and lowercase forms present.
2Using a HashMap allows for efficient counting and checking of character occurrences.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.