Skip to content

1763. Longest Nice Substring

  • Time: $O(n\log n) \to O(n^2)$
  • Space: $O(n\log n) \to O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  string longestNiceSubstring(string s) {
    if (s.length() < 2)
      return "";

    unordered_set<char> seen{s.begin(), s.end()};

    for (int i = 0; i < s.size(); ++i)
      // If both upper and lower case letters exists in the string, keep moving,
      // else take the erroneous character as a partition and check for its left
      // and right parts to be nice strings.
      if (!seen.contains(toggleCase(s[i]))) {
        const string prefix = longestNiceSubstring(s.substr(0, i));
        const string suffix = longestNiceSubstring(s.substr(i + 1));
        return prefix.length() >= suffix.length() ? prefix : suffix;
      }

    return s;
  }

 private:
  char toggleCase(char c) {
    return islower(c) ? toupper(c) : tolower(c);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public String longestNiceSubstring(String s) {
    if (s.length() < 2)
      return "";

    Set<Character> seen = s.chars().mapToObj(c -> (char) c).collect(Collectors.toSet());

    for (int i = 0; i < s.length(); ++i)
      if (!seen.contains(toggleCase(s.charAt(i)))) {
        final String prefix = longestNiceSubstring(s.substring(0, i));
        final String suffix = longestNiceSubstring(s.substring(i + 1));
        return prefix.length() >= suffix.length() ? prefix : suffix;
      }

    return s;
  }

  private char toggleCase(char c) {
    return Character.isLowerCase(c) ? Character.toUpperCase(c) : Character.toLowerCase(c);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def longestNiceSubstring(self, s: str) -> str:
    if len(s) < 2:
      return ''

    seen = set(s)

    for i, c in enumerate(s):
      # If both upper and lower case letters exists in the string, keep moving,
      # else take the erroneous character as a partition and check for its left
      # and right parts to be nice strings.
      if c.swapcase() not in seen:
        prefix = self.longestNiceSubstring(s[:i])
        suffix = self.longestNiceSubstring(s[i + 1:])
        return max(prefix, suffix, key=len)

    return s