1763. Longest Nice Substring #

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.

Problem Summary #

When, for every type of letter contained in a string s, both its uppercase and lowercase forms appear in s, this string s is called a nice string. For example, “abABB” is a nice string because ‘A’ and ‘a’ both appear, and ‘B’ and ‘b’ also both appear. However, “abA” is not a nice string because ‘b’ appears, but ‘B’ does not.

Given a string s, return the longest nice substring of s. If there are multiple answers, return the one that appears earliest. If no nice substring exists, return an empty string.

Solution Ideas #

• Solution one: brute force. Enumerate every substring and determine whether this substring satisfies the definition of a nice string, i.e., whether both the uppercase and lowercase forms of each letter appear.
• Solution two: this solution is a slight optimization of solution one, using binary to record states. First construct binary state strings, then compare these binary strings directly.
• Solution three: divide and conquer. Use i as the split point to split the string in order. Determine separately whether the left and right strings satisfy the definition of a nice string. The separated left and right strings can continue to be divided. Continue until only one letter remains. Record the earliest occurring string during this process.

Code #

package leetcode

import "unicode"

// Solution 1: divide and conquer, time complexity O(n)
func longestNiceSubstring(s string) string {
	if len(s) < 2 {
		return ""
	}

	chars := map[rune]int{}
	for _, r := range s {
		chars[r]++
	}

	for i := 0; i < len(s); i++ {
		r := rune(s[i])
		_, u := chars[unicode.ToUpper(r)]
		_, l := chars[unicode.ToLower(r)]
		if u && l {
			continue
		}
		left := longestNiceSubstring(s[:i])
		right := longestNiceSubstring(s[i+1:])
		if len(left) >= len(right) {
			return left
		} else {
			return right
		}
	}
	return s
}

// Solution 2: use binary to represent state
func longestNiceSubstring1(s string) (ans string) {
	for i := range s {
		lower, upper := 0, 0
		for j := i; j < len(s); j++ {
			if unicode.IsLower(rune(s[j])) {
				lower |= 1 << (s[j] - 'a')
			} else {
				upper |= 1 << (s[j] - 'A')
			}
			if lower == upper && j-i+1 > len(ans) {
				ans = s[i : j+1]
			}
		}
	}
	return
}

// Solution 3: brute-force enumeration, time complexity O(n^2)
func longestNiceSubstring2(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		m := map[byte]int{}
		m[s[i]]++
		for j := i + 1; j < len(s); j++ {
			m[s[j]]++
			if checkNiceString(m) && (j-i+1 > len(res)) {
				res = s[i : j+1]
			}
		}
	}
	return res
}

func checkNiceString(m map[byte]int) bool {
	for k := range m {
		if k >= 97 && k <= 122 {
			if _, ok := m[k-32]; !ok {
				return false
			}
		}
		if k >= 65 && k <= 90 {
			if _, ok := m[k+32]; !ok {
				return false
			}
		}
	}
	return true
}