# Longest Nice Substring
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-nice-substring)
Canonical: https://scaleengineer.com/dsa/problems/longest-nice-substring
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute Force Enumeration
This approach systematically checks every possible substring of the input string `s`. For each substring, it verifies if it meets the criteria of a "nice" string. The longest nice substring found is recorded and returned. This is the most straightforward but least efficient method.
**Time:** O(N^3), where N is the length of the string. Generating all `O(N^2)` substrings, and for each substring of length `k`, the `isNice` check takes `O(k)` time. This leads to a total complexity of O(N^3). · **Space:** O(N), where N is the length of the string. This is for storing the character set for the longest possible substring. In practice, since the alphabet size is constant (52), the space for the set is O(1). The space for the result string can be up to O(N).
**Pros:** Simple to understand and implement.; Correctly handles all cases and constraints.
**Cons:** Highly inefficient due to its cubic time complexity.; Performs redundant computations by re-evaluating overlapping substrings multiple times.
### Explanation
The algorithm uses two nested loops to generate all substrings. The outer loop selects the starting index `i`, and the inner loop selects the ending index `j`. This results in `O(N^2)` substrings.

For each substring `sub = s.substring(i, j + 1)`, a helper function `isNice(sub)` is called. The `isNice` function works by first creating a set of all unique characters in the substring, which takes time proportional to the substring's length. Then, it iterates through this set. For each character, it checks if its corresponding uppercase or lowercase counterpart is also present in the set. If any character's pair is missing, the substring is not nice. This check also takes time proportional to the substring's length.

If a substring is found to be nice and its length is greater than the length of the longest nice substring found so far, it becomes the new longest. Since we iterate through substrings starting from index 0, the first longest one we find will be the earliest, satisfying the tie-breaker rule.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public String longestNiceSubstring(String s) {
        String longest = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (isNice(sub)) {
                    if (sub.length() > longest.length()) {
                        longest = sub;
                    }
                }
            }
        }
        return longest;
    }

    private boolean isNice(String str) {
        Set<Character> charSet = new HashSet<>();
        for (char c : str.toCharArray()) {
            charSet.add(c);
        }

        for (char c : charSet) {
            if (Character.isLowerCase(c)) {
                if (!charSet.contains(Character.toUpperCase(c))) {
                    return false;
                }
            } else { // isUpperCase
                if (!charSet.contains(Character.toLowerCase(c))) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize an empty string `longestNice` to store the result.
- Use a pair of nested loops to generate every possible substring of the input string `s`. The outer loop with index `i` determines the start of the substring, and the inner loop with index `j` determines the end.
- For each substring `sub`, create a helper function `isNice(sub)` to check if it's a nice string.
- Inside `isNice(sub)`:
  - Create a `HashSet` of all characters present in `sub` for efficient lookup.
  - Iterate through each character `c` in the set.
  - For each `c`, check if its case-swapped counterpart (e.g., 'a' for 'A', 'B' for 'b') is also present in the set.
  - If any character's counterpart is missing, the substring is not nice, so return `false`.
  - If all characters have their counterparts, the substring is nice; return `true`.
- If `isNice(sub)` returns `true` and the length of `sub` is greater than the length of `longestNice`, update `longestNice` to `sub`.
- After checking all substrings, return `longestNice`.

## Divide and Conquer
This approach is based on a key observation: if a character `c` exists in a string `s` but its case-counterpart does not, then `c` cannot be part of any nice substring. Such a character acts as a "splitter", dividing the problem into smaller, independent subproblems that can be solved recursively.
**Time:** O(N^2) in the worst case. At each level of recursion, we scan the string segment of length `k`, taking `O(k)` time. The recursion depth can be up to `O(N)`, leading to a total time of `O(N^2)`. For balanced splits, it would be `O(N log N)`. · **Space:** O(N) in the worst case. This is due to the recursion stack depth, which can go up to N if the string is split one character at a time (e.g., `s = "abacada..."`).
**Pros:** More efficient than the O(N^3) brute-force approach.; Provides an elegant recursive solution to the problem.; Often performs better than the worst-case, with an average time complexity closer to O(N log N) for balanced splits.
**Cons:** The worst-case time complexity is still O(N^2).; Recursion adds overhead and can lead to a deep recursion stack, consuming O(N) space in the worst case.
### Explanation
The core of this method is a recursive function that takes a string as input. First, it finds all unique characters in the current string segment and stores them in a set for quick lookups. Then, it iterates through the string segment. If it finds a character `s[i]` whose pair (e.g., `a` for `A`) is not in the set, it knows that `s[i]` cannot be in the result.

This "invalid" character at index `i` splits the string into two parts: the substring before `i` and the substring after `i`. The longest nice substring must lie entirely within one of these two parts. The algorithm then makes two recursive calls, one for the left part and one for the right part. It returns the longer of the two results. By prioritizing the left result in case of a tie, it correctly finds the earliest longest substring.

If the loop completes without finding any such "invalid" character, it means the entire current string segment is nice, and since we want the longest, we can return this segment itself.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public String longestNiceSubstring(String s) {
        if (s.length() < 2) {
            return "";
        }
        
        Set<Character> charSet = new HashSet<>();
        for (char c : s.toCharArray()) {
            charSet.add(c);
        }
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!charSet.contains(Character.toLowerCase(c)) || !charSet.contains(Character.toUpperCase(c))) {
                String s1 = longestNiceSubstring(s.substring(0, i));
                String s2 = longestNiceSubstring(s.substring(i + 1));
                return s1.length() >= s2.length() ? s1 : s2;
            }
        }
        
        return s;
    }
}
```
### Algorithm
- Define a recursive function, let's call it `findNice(s)`.
- **Base Case:** If the length of string `s` is less than 2, it cannot be nice, so return an empty string `""`.
- **Recursive Step:**
  - Create a `HashSet` containing all unique characters of `s`.
  - Iterate through the string `s` with an index `i`.
  - For each character `c` at `s[i]`, check if both its lowercase and uppercase versions are present in the `HashSet`.
  - If a character `c` is found whose pair is missing, this character cannot be part of any nice substring. It acts as a 'splitter'.
  - Recursively call `findNice` on the substring to the left of the splitter (`s.substring(0, i)`) and the substring to the right (`s.substring(i + 1)`).
  - Compare the lengths of the results from the two recursive calls and return the longer one. If their lengths are equal, return the one from the left to satisfy the 'earliest occurrence' rule.
- **Success Case:** If the loop completes without finding any splitter character, it means the entire string `s` is nice. Return `s`.

## Optimized Brute Force with Bitmasking
This approach improves upon the brute-force method by optimizing the check for a "nice" substring. Instead of re-evaluating each substring from scratch, it maintains state as it expands a window. It iterates through all possible starting points and, for each, expands an ending point, efficiently checking for the "nice" property in O(1) time using bitmasks.
**Time:** O(N^2). The two nested loops iterate through all `O(N^2)` substrings. The operations inside the inner loop (bit manipulation, comparison) are constant time, O(1). · **Space:** O(1). We only use a few integer variables to store the masks and indices, regardless of the input string size. The space for the returned substring is not counted as part of the auxiliary space complexity.
**Pros:** Optimal space complexity of O(1).; Time complexity of O(N^2) is efficient enough for the given constraints.; Iterative solution avoids recursion overhead, making it practically faster than the divide and conquer approach.
**Cons:** The time complexity is still O(N^2), which might be slow for very large N (though efficient enough for the given constraints).; The use of bitmasking might be slightly less intuitive than a direct character set comparison for some developers.
### Explanation
The algorithm uses two nested loops to define a sliding window `s[i..j]`. The outer loop fixes the start `i`, and the inner loop iterates the end `j` from `i` to the end of the string.

For each window starting at `i`, we use two integer bitmasks, `lowerMask` and `upperMask`, to keep track of the lowercase and uppercase characters seen so far within that window. As `j` increases, we encounter a new character `s[j]` and update the appropriate bitmask. This is an O(1) operation.

A substring `s[i..j]` is nice if and only if for every character type present, both its lowercase and uppercase forms are present. This translates to a simple and extremely fast check: `lowerMask == upperMask`. If this condition is met, we have found a nice substring. We then check if its length `(j - i + 1)` is greater than the maximum length found so far and update our answer if it is.

```java
class Solution {
    public String longestNiceSubstring(String s) {
        int n = s.length();
        if (n < 2) {
            return "";
        }
        
        int maxLen = 0;
        int startIdx = 0;
        
        for (int i = 0; i < n; i++) {
            int lowerMask = 0;
            int upperMask = 0;
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (Character.isLowerCase(c)) {
                    lowerMask |= (1 << (c - 'a'));
                } else {
                    upperMask |= (1 << (c - 'A'));
                }
                
                if (lowerMask == upperMask) {
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        startIdx = i;
                    }
                }
            }
        }
        
        return s.substring(startIdx, startIdx + maxLen);
    }
}
```
### Algorithm
- Initialize `maxLen = 0` and `startIdx = 0` to track the longest nice substring found.
- Use a nested loop structure. The outer loop with index `i` iterates from `0` to `N-1`, fixing the starting position of a potential substring.
- For each starting position `i`, initialize two integer bitmasks, `lowerMask` and `upperMask`, to zero.
- The inner loop with index `j` iterates from `i` to `N-1`, extending the end of the current substring.
- In the inner loop, for each character `c = s.charAt(j)`:
  - If `c` is a lowercase letter, set the corresponding bit in `lowerMask`. (e.g., for 'c', set the 2nd bit: `lowerMask |= (1 << ('c' - 'a'))`).
  - If `c` is an uppercase letter, set the corresponding bit in `upperMask`. (e.g., for 'C', set the 2nd bit: `upperMask |= (1 << ('C' - 'A'))`).
- After updating the masks, check if `lowerMask == upperMask`. This condition is true if and only if for every letter type present in the substring `s[i..j]`, both its lowercase and uppercase forms have appeared.
- If the condition is true and the current substring's length `(j - i + 1)` is greater than `maxLen`, update `maxLen` and `startIdx`.
- After the loops complete, return the substring `s.substring(startIdx, startIdx + maxLen)`.

# Solutions
### Java

```java
class Solution {
public
  String longestNiceSubstring(String s) {
    int n = s.length();
    int k = -1;
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      Set<Character> ss = new HashSet<>();
      for (int j = i; j < n; ++j) {
        ss.add(s.charAt(j));
        boolean ok = true;
        for (char a : ss) {
          char b = (char)(a ^ 32);
          if (!(ss.contains(a) && ss.contains(b))) {
            ok = false;
            break;
          }
        }
        if (ok && mx < j - i + 1) {
          mx = j - i + 1;
          k = i;
        }
      }
    }
    return k == -1 ? "" : s.substring(k, k + mx);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string longestNiceSubstring(string s) {
    int n = s.size();
    int k = -1, mx = 0;
    for (int i = 0; i < n; ++i) {
      unordered_set<char> ss;
      for (int j = i; j < n; ++j) {
        ss.insert(s[j]);
        bool ok = true;
        for (auto &a : ss) {
          char b = a ^ 32;
          if (!(ss.count(a) && ss.count(b))) {
            ok = false;
            break;
          }
        }
        if (ok && mx < j - i + 1) {
          mx = j - i + 1;
          k = i;
        }
      }
    }
    return k == -1 ? "" : s.substr(k, mx);
  }
};

```

### Python

```python
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

```