Longest Nice Substring

EASY

Description

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

Checkout 3 different approaches to solve Longest Nice Substring. Click on different approaches to view the approach and algorithm in detail.

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.

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).

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.

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);
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Longest Nice Substring. Click on different languages to view the code.

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);
  }
}

Video Solution

Watch the video walkthrough for Longest Nice Substring

Algorithms:

Divide and Conquer

Patterns:

Sliding WindowBit Manipulation

Data Structures:

Hash TableString