Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1763.html

1763. Longest Nice Substring

Level

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.

Example 4:

Input: s = “dDzeE”

Output: “dD”

Explanation: Both “dD” and “eE” are the longest nice substrings. As there are multiple longest nice substrings, return “dD” since it occurs earlier.

Constraints:

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

Solution

Loop over all possible substrings of s. For each substring, check whether it is nice by using a hash set. Among all nice substrings, find the one that is the longest and has the earliest occurrence.

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

    public boolean isNice(String s) {
        Set<Character> set = new HashSet<Character>();
        int length = s.length();
        for (int i = 0; i < length; i++)
            set.add(s.charAt(i));
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            char difCase = c <= 'Z' ? (char) (c + 'a' - 'A') : (char) (c - 'a' + 'A');
            if (!set.contains(difCase))
                return false;
        }
        return true;
    }
}

############

class Solution {
    public String longestNiceSubstring(String s) {
        int n = s.length();
        int k = -1;
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            int lower = 0, upper = 0;
            for (int j = i; j < n; ++j) {
                char c = s.charAt(j);
                if (Character.isLowerCase(c)) {
                    lower |= 1 << (c - 'a');
                } else {
                    upper |= 1 << (c - 'A');
                }
                if (lower == upper && mx < j - i + 1) {
                    mx = j - i + 1;
                    k = i;
                }
            }
        }
        return k == -1 ? "" : s.substring(k, k + mx);
    }
}

  • // OJ: https://leetcode.com/problems/longest-nice-substring/
// Time: O(N^2)
// Space: O(N)
class Solution {
    bool nice(string &s) {
        int up[26] = {}, low[26] = {};
        for (char c : s) {
            if (c >= 'A' && c <= 'Z') up[c - 'A'] = 1;
            else low[c - 'a'] = 1;
        }
        for (int i = 0; i < 26; ++i) {
            if (up[i] ^ low[i]) return false;
        }
        return true;
    }
public:
    string longestNiceSubstring(string s) {
        int N = s.size();
        for (int len = N; len >= 2; --len) {
            for (int i = 0; i <= N - len; ++i) {
                auto sub = s.substr(i, len);
                if (nice(sub)) return sub;
            }
        }
        return "";
    }
};

  • class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        n = len(s)
        ans = ''
        for i in range(n):
            lower = upper = 0
            for j in range(i, n):
                if s[j].islower():
                    lower |= 1 << (ord(s[j]) - ord('a'))
                else:
                    upper |= 1 << (ord(s[j]) - ord('A'))
                if lower == upper and len(ans) < j - i + 1:
                    ans = s[i : j + 1]
        return ans

############

# 1763. Longest Nice Substring
# https://leetcode.com/problems/longest-nice-substring/

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if len(s) < 2: return ""
        
        mp = set(list(s))

        for i,c in enumerate(s):
            if c.upper() in mp and c.lower() in mp: continue
            
            first = self.longestNiceSubstring(s[:i])
            second = self.longestNiceSubstring(s[i+1:])
            
            return max(first, second, key = len)
        
        return s


  • func longestNiceSubstring(s string) string {
	n := len(s)
	k, mx := -1, 0
	for i := 0; i < n; i++ {
		var lower, upper int
		for j := i; j < n; j++ {
			if unicode.IsLower(rune(s[j])) {
				lower |= 1 << (s[j] - 'a')
			} else {
				upper |= 1 << (s[j] - 'A')
			}
			if lower == upper && mx < j-i+1 {
				mx = j - i + 1
				k = i
			}
		}
	}
	if k < 0 {
		return ""
	}
	return s[k : k+mx]
}

  • function longestNiceSubstring(s: string): string {
    const n = s.length;
    let ans = '';
    for (let i = 0; i < n; i++) {
        let lower = 0,
            upper = 0;
        for (let j = i; j < n; j++) {
            const c = s.charCodeAt(j);
            if (c > 96) {
                lower |= 1 << (c - 97);
            } else {
                upper |= 1 << (c - 65);
            }
            if (lower == upper && j - i + 1 > ans.length) {
                ans = s.substring(i, j + 1);
            }
        }
    }
    return ans;
}

All Problems

All Solutions