#1763

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Longest Nice Substring

Find the longest nice substring in a given string using the sliding window technique with running state updates.

hash table string divide and conquer bit manipulation sliding window

Problem Statement

A string is considered nice if, for every letter it contains, both the uppercase and lowercase versions of that letter are present. For example, the string 'abABB' is nice because 'A' and 'a' both appear, and 'B' and 'b' both appear. Conversely, 'abA' is not nice because while 'a' appears, 'B' does not. Given a string s, your task is to return the longest nice substring of s. If there are multiple possible longest substrings, return the earliest one. If no nice substring exists, return an empty string.

You are asked to solve the problem by finding the longest nice substring in an efficient manner. A brute force approach would involve checking every substring, but that can be optimized using a sliding window with running state updates. You will need to ensure that each character appears in both uppercase and lowercase in the substring.

Examples

Example 1

Input: s = "YazaAay"

Output: "aAa"

"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"

"Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Example 3

Input: s = "c"

Output: ""

There are no nice substrings.

Constraints

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

Solution Approach

Sliding Window with Running State Updates

Start with a sliding window approach, where you expand the window while ensuring that for each character in the window, its uppercase and lowercase version are both present. Use a hash set or array to track the characters in the current window. If the condition is violated, move the left boundary of the window until it becomes valid again.

Optimizing with Early Stopping

Instead of checking all possible substrings, focus on expanding and contracting the sliding window as you iterate through the string. Once a valid window is found, try to extend it to include more characters. If the window becomes invalid, shrink it from the left until it becomes valid again, thus ensuring an efficient check for the longest nice substring.

Edge Case Handling

Handle edge cases such as strings of length 1 or strings that contain no valid nice substrings. Also, ensure that the solution accounts for the possibility of multiple substrings of the same length, returning the one that appears first in the string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the string, because we process each character at most twice (once when expanding the window and once when shrinking it). The space complexity is O(k), where k is the number of unique characters in the string, since we need to store the state of characters within the sliding window.

What Interviewers Usually Probe

Checks if the candidate understands the sliding window technique with dynamic state updates.
Tests the candidate's ability to optimize brute force approaches into efficient solutions.
Looks for a clear explanation of edge cases and handling them correctly.

Common Pitfalls or Variants

Common pitfalls

Not correctly tracking the running state of characters inside the sliding window.
Failing to handle edge cases, such as strings that have no nice substrings or strings of length 1.
Using a brute force approach without optimizing the substring search using the sliding window.

Follow-up variants

Consider optimizing this solution further for larger strings or varying constraints.
Try solving the problem using a divide and conquer strategy.
Explore the possibility of using bit manipulation for state representation.

FAQ

How does the sliding window work in the Longest Nice Substring problem?

The sliding window expands as you find valid characters in the substring and shrinks when an invalid character is encountered. This helps efficiently find the longest nice substring.

What is a nice string in the Longest Nice Substring problem?

A string is nice if each character in the string has both its uppercase and lowercase form present, such as 'a' and 'A' or 'b' and 'B'.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string, because each character is processed at most twice.

Can I solve this problem using a brute force approach?

Yes, but the brute force approach would be inefficient. The sliding window technique is a more optimized solution.

How can I handle strings with no nice substrings?

If no nice substring is found, return an empty string. This is a simple edge case to check for in the solution.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        n = len(s)
        ans = ''
        for i in range(n):
            ss = set()
            for j in range(i, n):
                ss.add(s[j])
                if (
                    all(c.lower() in ss and c.upper() in ss for c in ss)
                    and len(ans) < j - i + 1
                ):
                    ans = s[i : j + 1]
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        n = len(s)
        ans = ''
        for i in range(n):
            ss = set()
            for j in range(i, n):
                ss.add(s[j])
                if (
                    all(c.lower() in ss and c.upper() in ss for c in ss)
                    and len(ans) < j - i + 1
                ):
                    ans = s[i : j + 1]
        return ans

Continue Practicing

#1016 binary string with substrings representing 1 to n #1684 count the number of consistent strings #1876 substrings of size three with distinct characters