Leetcode 1763: Longest Nice Substring
A string is considered nice if every letter that appears in the string appears both in uppercase and lowercase. For example, ‘aA’ and ‘bB’ are nice strings, but ‘a’ and ‘B’ are not. Given a string s, find the longest nice substring of s. If there are multiple longest nice substrings, return the one that appears first. If no nice substring exists, return an empty string.
Problem
Approach
Steps
Complexity
Input: The input is a string s consisting of uppercase and lowercase English letters.
Example: Input: s = 'aAAbB'
Constraints:
• 1 <= s.length <= 100
• s consists of uppercase and lowercase English letters.
Output: Return the longest nice substring. If no such substring exists, return an empty string.
Example: Output: 'aA'
Constraints:
Goal: The goal is to find the longest substring where every letter appears in both its lowercase and uppercase form.
Steps:
• 1. Iterate through all possible substrings of the given string s.
• 2. For each substring, check if it contains every letter in both uppercase and lowercase.
• 3. Keep track of the longest valid substring found during the iteration.
Goal: The solution should efficiently handle strings of length up to 100.
Steps:
• The solution should perform efficiently even for the maximum length of the string (100 characters).
Assumptions:
• The string contains only alphabetic characters (both uppercase and lowercase).
• There are no special characters or spaces in the string.
• Input: Input: s = 'YazaAay'
• Explanation: The substring 'aAa' is a nice string because both 'A' and 'a' appear. 'aAa' is the longest nice substring.
• Input: Input: s = 'Bb'
• Explanation: The entire string 'Bb' is a nice string because both 'B' and 'b' appear.
• Input: Input: s = 'c'
• Explanation: There are no nice substrings because 'c' does not have a corresponding uppercase letter.
Approach: We can solve the problem by using recursion to check for all substrings, and for each substring, verify if it is nice.
Observations:
• A string is nice if it contains all letters in both their uppercase and lowercase forms.
• We need to explore all possible substrings to find the longest nice substring.
• We can approach this by checking each possible substring, but optimize by eliminating invalid substrings early.
Steps:
• 1. Use a recursive approach to find all possible substrings.
• 2. For each substring, check if it satisfies the nice condition, i.e., each character appears both in uppercase and lowercase.
• 3. Track the longest nice substring and return it as the result.
Empty Inputs:
• If the input string is empty, return an empty string.
Large Inputs:
• For larger inputs, the solution should efficiently process the string to find the longest nice substring.
Special Values:
• If the string contains only one type of letter (like 'a' or 'A'), no nice substring will exist.
Constraints:
• The solution should efficiently handle strings with a maximum length of 100.
string longestNiceSubstring(string s, int start = 0, int end = -1) {
if (end == -1)
end = s.size();
int cnt[26][2] = {}, j = start - 1;
for (auto i = start; i < end; ++i)
cnt[tolower(s[i]) - 'a'][(bool)islower(s[i])] = 1;
string res;
for (auto i = start; i <= end; ++i) {
int ch = i == end ? -1 : tolower(s[i]) - 'a';
if (ch == -1 || cnt[ch][0] + cnt[ch][1] == 1) {
if (j == -1 && ch == -1)
return s;
auto res1 = longestNiceSubstring(s.substr(j + 1, i - j - 1));
if (res1.size() > res.size())
res = res1;
j = i;
}
}
return res;
}
1 : Function Declaration
string longestNiceSubstring(string s, int start = 0, int end = -1) {
Declares the function that finds the longest nice substring of a given string.
2 : Condition Check
if (end == -1)
Checks if the end index is unset and initializes it to the string size.
3 : Initialization
end = s.size();
Sets the end of the substring to the size of the input string if not provided.
4 : Array Initialization
int cnt[26][2] = {}, j = start - 1;
Initializes a 2D array to track lowercase and uppercase occurrences of characters and a pointer `j` for substring processing.
5 : For Loop
for (auto i = start; i < end; ++i)
Iterates over the string to populate the character tracking array.
6 : Tracking
cnt[tolower(s[i]) - 'a'][(bool)islower(s[i])] = 1;
Marks the presence of lowercase or uppercase forms of the current character in the tracking array.
7 : Variable Initialization
string res;
Initializes an empty string `res` to store the result substring.
8 : For Loop
for (auto i = start; i <= end; ++i) {
Iterates through the string to identify and process substrings.
9 : Condition Check
int ch = i == end ? -1 : tolower(s[i]) - 'a';
Gets the character index or sets a sentinel value when the end of the string is reached.
10 : Condition Check
if (ch == -1 || cnt[ch][0] + cnt[ch][1] == 1) {
Identifies substrings that are not nice due to missing uppercase or lowercase forms.
11 : Edge Case
if (j == -1 && ch == -1)
Handles the edge case where the entire string is a nice substring.
12 : Return Statement
return s;
Returns the string if it is a nice substring.
13 : Recursive Call
auto res1 = longestNiceSubstring(s.substr(j + 1, i - j - 1));
Recursively processes substrings to find the longest nice substring.
14 : Comparison
if (res1.size() > res.size())
Checks if the current result is longer than the previous best result.
15 : Update Result
res = res1;
Updates the result with the longer substring.
16 : Pointer Update
j = i;
Moves the pointer `j` to the current index for the next substring.
17 : Return Statement
return res;
Returns the longest nice substring found.
Best Case: O(n)
Average Case: O(n^2)
Worst Case: O(n^3)
Description: The time complexity is driven by the recursive checking of substrings and the verification process for each substring, resulting in O(n^3) in the worst case.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) in the worst case due to the recursion stack and storing the substrings.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus