algoadvance

Leetcode 1763. Longest Nice Substring

Problem Statement:

A string s is considered nice if, for every character in s, the corresponding uppercase and lowercase characters both exist in s.

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 no nice substrings, return an empty string.

Example:

  1. Input: s = “YazaAay” Output: “aAa”
  2. Input: s = “Bb” Output: “Bb”
  3. Input: s = “c” Output: “”

Clarifying Questions:

  1. Is the input string guaranteed to be non-empty?
    • Yes, the input string s will always have at least one character.
  2. Are we considering case sensitivity for characters?
    • Yes, the problem explicitly specifies lowercase and uppercase pairs.
  3. Should the solution account for non-alphabet characters?
    • No, the problem is framed around alphabetic (A-Z, a-z) characters only.

Strategy:

  1. Recursive Approach:
    • If the string s itself is nice, return it.
    • Otherwise, split the string at points where it fails the niceness condition and recurse on those substrings.
    • Keep track of the longest nice substring found during recursion.
  2. Helper Functions:
    • A function to check if a string is nice.
    • A function to find and return the longest nice substring using recursion.

Time Complexity:

Code:

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

// Helper function to check if a string is nice
bool isNice(const string &s) {
    unordered_set<char> charset(s.begin(), s.end());
    for (char c : charset) {
        if ((isupper(c) && charset.count(tolower(c)) == 0) || 
            (islower(c) && charset.count(toupper(c)) == 0)) {
            return false;
        }
    }
    return true;
}

// Recursive function to find the longest nice substring
string longestNiceSubstring(const string &s) {
    int n = s.length();
    if (n < 2) return "";

    // If the entire string is nice, return it
    if (isNice(s)) return s;

    // Try to find the longest nice substring by splitting
    for (int i = 0; i < n; ++i) {
        string left = s.substr(0, i);
        string right = s.substr(i + 1, n - i - 1);

        if (!isNice(s.substr(i, 1))) {
            string longestLeft = longestNiceSubstring(left);
            string longestRight = longestNiceSubstring(right);
            return longestLeft.length() >= longestRight.length() ? longestLeft : longestRight;
        }
    }
    
    return "";
}

int main() {
    string s;
    cout << "Enter the string: ";
    cin >> s;
    string result = longestNiceSubstring(s);
    cout << "Longest Nice Substring: " << result << endl;
    return 0;
}

Explanation:

  1. isNice Function:
    • Check each character if its case counterpart exists in the string.
  2. longestNiceSubstring Function:
    • Use recursion to split when a character violates niceness.
    • Compare between left and right substrings and return the longer one.

This ensures that the solution finds the longest nice substring by systematically breaking down the problem using a divide-and-conquer approach.

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