algoadvance

Leetcode 1763. Longest Nice Substring

Problem Statement

Given a string s, return the longest substring of s that is a “nice” substring. A “nice” substring is a string where, for every letter in that substring, the corresponding uppercase or lowercase letter also exists in the substring. If there are multiple longest “nice” substrings, return the one that appears first. If there are none, return an empty string.

Clarifying Questions

  1. Input Constraints:
    • Is the input guaranteed to be non-null?
    • What is the maximum length of the input string s?
  2. Output Requirements:
    • If there are multiple substrings of the same maximum length that are “nice”, do we need to return the first one encountered?
  3. Edge Cases:
    • How should we handle strings with no “nice” substrings?
    • How should we treat empty strings?

Based on the prompt, I’ll assume:

Strategy

The solution to this problem can be approached using the following steps:

  1. Substrings Generation:
    • Generate all possible substrings of s.
  2. Check for “Nice” Property:
    • For each substring, check whether it satisfies the “nice” property.
  3. Track Longest Substring:
    • Keep track of the longest substring that satisfies the “nice” property.

For checking the “nice” property, we can use a set to record the presence of characters in both their uppercase and lowercase forms. If all characters in a substring have both their uppercase and lowercase counterparts, the substring is considered “nice”.

Code

public class Solution {
    public String longestNiceSubstring(String s) {
        int n = s.length();
        String longestNiceSubstring = "";

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                String substring = s.substring(i, j);
                if (isNice(substring) && substring.length() > longestNiceSubstring.length()) {
                    longestNiceSubstring = substring;
                }
            }
        }

        return longestNiceSubstring;
    }

    private boolean isNice(String str) {
        Set<Character> set = new HashSet<>();
        for (char ch : str.toCharArray()) {
            set.add(ch);
        }
        for (char ch : str.toCharArray()) {
            if (!set.contains(Character.toUpperCase(ch)) || !set.contains(Character.toLowerCase(ch))) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "YazaAay";
        System.out.println("Longest Nice Substring: " + solution.longestNiceSubstring(s));
    }
}

Time Complexity

Combining these complexities, the overall time complexity is:

This is because for each of the ( \frac{n(n+1)}{2} \approx O(n^2) ) substrings, we are performing a (O(n)) check.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI