Leetcode problem 105 - Longest Nice Substring

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.

/**
 * @param {string} s
 * @return {string}
 */
var longestNiceSubstring = function (s) {
  // Initialize a variable to store the answer
  let ans = "";
  // Outer loop to iterate through each starting index in the string 's'
  for (let i = 0; i < s.length; i++) {
    // Inner loop to iterate through each ending index in the string 's'
    for (let j = i + 1; j < s.length + 1; j++) {
      // Extract the substring from index i to j
      let substring = s.substring(i, j);

      // Map each character in the substring to its inverted case equivalent
      let invertedCaseChars = [...substring].map((str) => {
        const characters = str.split("");

        // Use ternary operator to swap case of each character
        const swappedCharacters = characters.map((char) =>
          char === char.toUpperCase() ? char.toLowerCase() : char.toUpperCase()
        );
        // Join the characters back into a string
        return swappedCharacters.join("");
      });

      // Check if every inverted case character is included in the substring
      if (invertedCaseChars.every((char) => substring.includes(char))) {
        // Update 'ans' if the current substring is longer than the current answer
        ans = substring.length > ans.length ? substring : ans;
      }
    }
  }
  // Return the final answer
  return ans;
};

The time complexity of this code is O(n^3), where n is the length of the input string s. This is because there are two nested loops iterating over the string, and for each substring, there is another loop iterating over the characters to invert their case. Therefore, the overall time complexity is O(n^3).

The space complexity of this code is O(n), where n is the length of the input string s. This is because the code uses additional space to store the inverted case characters for each substring. The maximum number of inverted case characters for a substring is equal to the length of the substring itself. Therefore, the overall space complexity is O(n).