Longest Nice Substring LeetCode Solution

Difficulty Level Easy
Frequently asked in MicrosoftViews 4854

Problem Statement :

Longest Nice Substring LeetCode Solution – 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 :

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 :

Longest Nice Substring LeetCode Solution

Explanation :

  • We need to return the longest substring of s that is nice.
  • A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase.
  • If we will find multiple answers,  then we need to return the substring of the earliest occurrence. If there are none, return an empty string.

Approach :

  • At First, we need to figure out, how can we check if the string is nice or not.
  • For checking whether the string is nice or not, we can use a set, if no uppercase or lowercase characters of any alphabets are present in the set, it means string s is not a nice string.
  • If the string is nice, means all alphabets present in the string have lowercase and uppercase alphabets then return that String, as we need to return the longest nice substring.
  • If the string is not nice, there is a character that prevents the entire string from being as nice.

  • so, the only way to find a nice substring is to exclude this char, which means you split the string at that character say x, something like [start…]x[…end]

  • Now, we have two sub-problems with the left and right subproblems. So, to find the original Longest Nice Substring problem,  we can recursively approach it. This is the very definition of the Divide-and-Conquer technique – A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Code :

Java  Code  Longest Nice Substring :

class Solution {
  public String longestNiceSubstring(String s) {
  int[] niceSubstring = longestNiceSubstring(s,0,s.length()-1);
  return s.substring(niceSubstring[0], niceSubstring[1]+1);
}
    
private int[]  longestNiceSubstring(String s,int left,int right) {
  int splittingIndex=isNotNiceString(s,left,right);
if(splittingIndex==-1)return  new int[]{left, right};
            int[]  leftString = longestNiceSubstring(s,left,splittingIndex-1);
      int[]  rightString = longestNiceSubstring(s,splittingIndex+1,right);
      return  (leftString[1]-leftString[0]>= rightString[1]-rightString[0]) ? leftString : rightString;

}
    
private int isNotNiceString(String s,int left,int right) {
        Set<Character> set = getCharacterSet(s,left,right);    
        for (int i = left; i <=right; i++) {
            char ch = s.charAt(i);
            if (!set.contains(Character.toLowerCase(ch)) || !set.contains(Character.toUpperCase(ch))) {
                return i;
            }
        }
        return -1;
    }
    
private Set<Character> getCharacterSet(String s, int left, int right) {
  Set<Character> charSet = new HashSet<Character>();
  for (int i = left; i <= right; i++){
    charSet.add(s.charAt(i));
    }
  return charSet;
}
}

C++ Code  Longest Nice Substring :

class Solution {
public:
    string longestNiceSubstring(string s) {
          
   pair<int,int> niceSubstring = longestNiceSubstring(s,0,s.length()-1);
  return s.substr(niceSubstring.first, niceSubstring.second-niceSubstring.first+1);
}
    
 pair<int,int> longestNiceSubstring(string&s,int left,int right) {
  int splittingIndex=isNotNiceString(s,left,right);
     pair<int,int> rez = {left,right};
if(splittingIndex==-1)return  rez;
            pair<int,int> leftString = longestNiceSubstring(s,left,splittingIndex-1);
      pair<int,int> rightString = longestNiceSubstring(s,splittingIndex+1,right);
      return  (leftString.second-leftString.first>= rightString.second-rightString.first) ? leftString : rightString;

}
    
 int isNotNiceString(string&s,int left,int right) {
       unordered_set<char>  set = getCharacterSet(s,left,right);    
        for (int i = left; i <=right; i++) {
            char ch = s[i];
            if (set.find(toupper(ch))==set.end() ||set.find(tolower(ch))==set.end()) {
                return i;
            }
        }
        return -1;
    }
    
  unordered_set<char> getCharacterSet(string&s, int left, int right) {
   unordered_set<char>charSet; 
  for (int i = left; i <= right; i++){
    charSet.insert(s[i]);
    }
  return charSet;
} 
    
};

Complexity Analysis for Longest Nice Substring LeetCode Solution:

Time Complexity

O(n) , since, Divide and conquer recursive approach will traverse length of the string.

Space Complexity 

O(1) , apart from recursion stack space, at most  52 uppercase and lowercase alphabets will be present in the set.

 

Translate »