Leetcode 358: Rearrange String K Distance Apart

 https://leetcode.com/problems/find-latest-group-of-size-m/description/

Notes:

This question is very similar as another question Leetcode 621 (since I solved that question first...)

The basic idea is the same: we need to find the letter with the largest count (m), then for the first (m-1) we have to place (m-1)*k letters (including the letter with the maximum count). 

Then for the last one letter, we do not need to keep it k distance apart from the next one (since there is no next one...). If there is no letter with the tied maximum counting, we just need to add 1 (the letter itself), but if there are n letters with the maximum counting, then the need to add n more letters, to list all the letter with k distance apart.

The overall letters need are (m-1)*k + n. If this value is larger than the size of the string, then there is not enough letters to maintain k distance apart: means that this is impossible. Otherwise, it is okay to form an valid one.

Since this question requests to return one final string, so we can consider to use a priority queue for valid ones: 

1): every time, we pick up one with the largest counting; 

2): and we keep this until we have pop out k different letters. This will form one valid "k-distance" apart substring; 

3): then we need to put the previous pop-out elements back to the priority queue, if their size still larger than 1 after removing 1.

4): repeat this process until there is no element remaining in the queue.

See the code below:

class Solution {
public:
    string rearrangeString(string str, int k) {
        if (k == 0) return str;
        string res;
        int len = (int)str.size(), mx = 0, rep = 0;
        unordered_map<char, int> m;
        priority_queue<pair<int, char>> q;
        for (auto a : str) ++m[a];
        for (auto it = m.begin(); it != m.end(); ++it) {
            q.push({it->second, it->first});
            // find the maximum counting, and the numer of letters having this 
	    if (it->first > mx) {
                mx = it->first;
                rep = 1;
	    } else if (it->first == mx) {
                ++rep;   
            }
        }
        // if need more letters than itself, then cannot construct an valid one
        if((m-1)*k + rep > len) return "";
        while (!q.empty()) {
            vector<pair<int, int>> v;
            int cnt = min(k, len);
            for (int i = 0; i < cnt; ++i) {
                if (q.empty()) return "";
                auto t = q.top(); q.pop();
                res.push_back(t.second);
                if (--t.first > 0) v.push_back(t);
                --len;
            }
            for (auto a : v) q.push(a);
        }
        return res;
    }
};

 

Leetcode 71: Simplify Path

https://leetcode.com/problems/simplify-path/description/

Notes:

The question is straightforward, see the pseudo-code below:

def res = "";
if s[i] == '/'
         continue;
else
         def t = the following string;
         if t == ".."
                    if(res.size()) pop out the least element from res.
         else if t == "." continue;
         else
                   save '/' and t into res;
return res

See the code below:

class Solution {
public:
    string simplifyPath(string path) {
        string res = "";
        if(path.empty()) return res;
        for(int i=0; i<path.size(); ) {
            if(path[i] != '/') {
                string t = "";
                while(i<path.size() && path[i] != '/') {
                    t.push_back(path[i++]);
                }
                if(t == "..") {
                    while(res.size() && res.back() != '/') res.pop_back();
                    if(res.size() && res.back() == '/') res.pop_back();
                }
                else if(t != ".") {
                    res.push_back('/');
                    res += t;
                }
            }
            else ++i;
        }
        if(res.empty()) res = "/";
        return res;
    }
};

Leetcode 1268: Search Suggestions System

https://leetcode.com/problems/search-suggestions-system/description/

Notes:

This question can be solved without Trie.

We just need to find the sorted strings with the same prefix. So it is pretty straightforward after sorting the strings.

See the code below:

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        int n = searchWord.size();
        vector<vector<string>> res(n);
        sort(products.begin(), products.end());
        for(int i=0; i<n; ++i) {
            string w = searchWord.substr(0, i+1);
            auto it = lower_bound(begin(products), end(products), w);
            for(; it != end(products) && it->substr(0, i+1) == w && res[i].size() < 3; ++it){
                res[i].push_back(*it);
            }
        }
        return res;
    }
};

The above code has a time complexity of O(nlogn), space complexity of O(1).

Another way is that we can use a hash map to record the string with the same prefix. Then we just need to choose the first three strings at each specific prefix.

See the code below:

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        vector<vector<string>> res;
        unordered_map<string, multiset<string>> mp;
        for(auto &a : products) {
            for(int i=0; i<a.size(); ++i) {
                string b = a.substr(0, i+1);
                mp[b].insert(a);
            }
        }
        for(int i=0; i<searchWord.size(); ++i) {
            string key = searchWord.substr(0, i+1);
            res.push_back(vector<string>(mp[key].begin(), mp[key].size()<3 ? mp[key].end() : next(mp[key].begin(), 3)));
        }
        return res;
    }
};

Leetcode 647: Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/description/

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

1. The input string length won't exceed 1000.

Notes:

This question asks for all the palindromic substrings. So what we need to do is to develop an effective way to count them, and at the same time to avoid repeating count.

There are two types of strings: one is with size of odd number; the other one is with size of even number.

So at position i, we can choose:

1: choose s[i] as the center element, the final size is odd;

2: choose s[i-1] and s[i] as the center elements, the final size is even.

See the code below:

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0, len = s.size();
        for(int i=0; i<len; ++i) {
            ++res;
            int j = 1;
            while(i-j >=0 && i+j <len && s[i-j] == s[i+j]) {
                ++res;
                ++j;
            }
            if(i-1>=0) {
                int j = 0;
                while(i-1-j >=0 && i+j <len && s[i-1-j] == s[i+j]) {
                    ++res;
                    ++j;
                }
            }
        }
        return res;
    }
};

Leetcode 1081: Smallest Subsequence of Distinct Characters

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/description/

Notes:

This question is the same as another question Leetcode 316. Please refer to that post for the analysis.

Here two other methods are shared below.

The first one is by analyze the indexes of all the letter. The basic logic is that: start with the smallest letter, if its first index is smaller than all the last indexes of all the rest letters, then it definitely will be the first one to choose. If the smallest does not fit with this condition, meaning there are some larger letter ends earlier than it. So we simply move on to the second smallest one, and so on.

Once we find the first letter, we need to update the indexes. Basically, all the indexes of this letter will not be considered any more; and all the indexes of all the rest letters which are smaller than chosen index can be removed. There is no need to consider them more.

See the code below:

class Solution {
public:
    string smallestSubsequence(string text) {
        string res = "";
        vector<vector<int>> ids(26);//the indexes of letter
        int ct = 0;//the number of unique letters
        for(int i=0; i<text.size(); ++i) {
            if(ids[text[i]-'a'].empty()) ++ct;
            ids[text[i]-'a'].push_back(i);
        }
        vector<int> used(26, 0);//label whether in the res or not
        while(ct>0) {
            int last_min = 1001;// the minimum of the last index of each letter
            for(int i=0; i<26; ++i) {
                if(ids[i].empty() || used[i]) continue;
                last_min = min(last_min, ids[i].back());
            }
            int pos = 0;
            for(int i=0; i<26; ++i) {//find the samllest letter shows on the left of all the rest letters
                                     //or the smallest letter whose smallest index is smaller than
                                     //all the last indexes of all the rest letters
                if(ids[i].empty() || used[i]) continue;
                if(ids[i].front()<=last_min) {
                    pos = i;
                    break;
                }
            }
            res.push_back(pos+'a');
            used[pos] = 1;
            for(int i=0; i<26; ++i) {//remove all the indexes which are smaller than ids[pos].front()
                if(ids[i].empty() || used[i]) continue;
                while(ids[i].size() && ids[i].front() < ids[pos].front()) ids[i].erase(ids[i].begin());
            }          
            --ct;
        }
        return res;
    }
};

So one thing from the above code can be seen is that the last index of each letter is important. Follow this line, we can develop another solution.

Let find the last index of each letter first.

Then scan the string. For each letter, we just need to check the range of current position to its last index.

If there is a smaller letter found between, meaning the smaller letter can be before the current letter; so give up the current letter temporally;

If there is a larger letter found between, we need to consider two situations:

one is that the last index of the larger letter is larger than that of the current letter. For this case we just can continue, because the larger letter will show up latter;

the other case is the opposite, meaning that the larger letter ends up earlier than the current letter. In this case, we need to shorten the search range, because the early termination of a larger letter means that we have to stop to take the larger letter in the final result before going to further. Of course, the current letter which is smaller should be put before the larger letter.

See the code below:

class Solution {
public:
    string smallestSubsequence(string text) {
        string res = "";
        int len = text.size();
        vector<int> ct(26, -1);
        for(int i=0; i<text.size(); ++i){
            ct[text[i]-'a'] = i;
        }
        for(int i=0; i<text.size(); ++i){
            int right = ct[text[i]-'a'];
            if(right == -1) continue;
            bool find = true;
            for(int j=i+1; j<right; ++j){
                if(ct[text[j]-'a'] == -1 || text[j] == text[i]) continue;
                if(text[j] > text[i] && ct[text[j]-'a'] < right) right = ct[text[j]-'a'];
                if(text[j] < text[i]) {find = false; break;}
            }
            if(find) {res.push_back(text[i]); ct[text[i]-'a'] = -1;}
        }
        return res;
    }
};

Leetcode 316: Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/description/

Notes:

This question is same as Leetcode 1081, which essentially asks for the same thing.

The native response is to find the smaller[i] at the most-left position first. But before the smaller s[i], when we meet with a larger letter, we need to know whether there are still some in the remaining string after the smaller[i]. If true, we can simply ignore the larger one temporally since there are still some in the remaining part.

How do we know whether there are still some in the remaining string after the smaller[i]? One way is that we can count the number of each letter firstly. Then as scanning through the string, we know exactly how many are left to each letter.

See the code below:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res = "";
        vector<int> ct(26, 0), used(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        for(auto &a : s) {
            --ct[a-'a'];
            if(used[a-'a']++ >0) continue;//once already in the res, no need to run again
            while(res.size() && res.back() > a && ct[res.back() - 'a']) {
                used[res.back() - 'a'] = 0;//once pop, is not in the res anymore
                res.pop_back();
            }
            res.push_back(a);
        }
        return res;
    }
};

Another way is to solve this problem recursively: Scan the array greedily, we need to localize the most-left smallest s[i]. But as analyzed above, the requirement for continuing the scanning of the string is that, there are still some in the remaining part of the string. Once this condition become non valid, we can

1): put s[i] into the answer;
2): remove all the elements before s[i]; (why? because there are still some after s[i])
3): remove all the rest s[i] in the remaining string;
4): recursive check the remaining string.

See the code below:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        if(s.size() < 2) return s;
        vector<int> ct(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        int pos = 0;
        for(int i=0; i<s.size(); ++i) {
            if(s[i] < s[pos]) pos = i; //the most-left smallest s[i];
            if(--ct[s[i]-'a'] == 0) break; //no more left in the remaining string.
        }
        for(int i=pos+1; i<s.size(); ++i) {//remove extra s[i]
            if(s[i] == s[pos]) {
                s.erase(i, 1);
                --i;
            }
        }
        return s[pos] + removeDuplicateLetters(s.substr(pos+1));
    }
};

The time complexity of the above recursive code is till O(N) or O(26*N). (each letter at most check 1 time)

Leetcode 792: Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/description/

Notes:

This question is the same as the follow up question of Leetcode 392.

See the code below:

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        int res = 0;
        vector<vector<int>> ids(26);
        for(int i=0; i<S.size(); ++i) ids[S[i]-'a'].push_back(i);
        for(auto &w : words) {
            if(w.size() > S.size()) continue;
            int id = -1, i = 0;
            for(; i<w.size(); ++i) {
                int t = w[i] - 'a';
                auto it = upper_bound(ids[t].begin(), ids[t].end(), id);
                if(it == ids[t].end()) break;
                id = *it;
            }
            if(i == w.size()) ++res;
        }
        return res;
    }
};

Leetcode 1055: Shortest Way to Form String

Constraints:

• Both the source and target strings consist of only lowercase English letters from "a"-"z".
• The lengths of source and target string are between 1 and 1000.

Notes:

The algorithm to this question is pretty straightforward: greedy. Scan target from left: as along as it is a sub-sequence of source, continue the scan. When it reaches the end of source, it means that we have to adopt another subsequence of source to form the rest part of target. so we simply update the count by adding 1, and continue the above process until finishing the scan.

This question can be view as a follow up to question Leetcode 392 and Leetode 792

See the code below:

class Solution {
public:
    int shortestWay(string source, string target) {
        int res = 0;
        vector<vector<int>> ids(26);//used to record the ids of each letter in source
        for(int i=0; i<source.size(); ++i) {
            ids[source[i]-'a'].push_back(i);
        }
        int idx = -1;
        bool cannot = false;
        for(int i=0; i<target.size(); ++i) {
            int j = target[i] - 'a';
            if(ids[j].empty()) {
                cannot = true;
                break;
            }
            auto it = upper_bound(ids[j].begin(), ids[j].end(), idx);//the first bigger than idx
            if(it == ids[j].end()) {
                ++res;
                idx = -1;
                --i;//target[i] is not matched yet
                continue;
            }
            idx = *it;
            if(idx+1==source.size()) {
                ++res;
                idx = -1;
            }
        }
        if(idx != -1) ++res; //the last remaining part of source
        return (cannot || !res) ? -1 : res;
    }
};

The code can be modified as:

class Solution {
public:
    int shortestWay(string source, string target) {
        int res = 0;
        vector<vector<int>> ids(26);//used to record the ids of each letter in source
        for(int i=0; i<source.size(); ++i) {
            ids[source[i]-'a'].push_back(i);
        }
        int idx = -1;
        bool cannot = false;
        for(int i=0; i<target.size(); ++i) {
            int j = target[i] - 'a';
            if(ids[j].empty()) {
                cannot = true;
                break;
            }
            auto it = upper_bound(ids[j].begin(), ids[j].end(), idx);//the first bigger than idx
            if(it != ids[j].end()) idx = *it;
            if(it == ids[j].end() || idx+1==source.size()) {
                if(it == ids[j].end()) --i;//target[i] is not matched yet
                ++res;
                idx = -1;
            }
        }
        if(idx != -1) ++res; //the last remaining part of source
        return (cannot || !res) ? -1 : res;
    }
};

Leetcode 392: Is Subsequence

https://leetcode.com/problems/is-subsequence/description/

Notes:

This question is an easy question. Using the so-called two-pointer method. The key is the follow-up question.

See the code below:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0;
        for(; j<t.size(); ++j) {
            if(s[i] == t[j]) ++i;
            if(i == s.size()) return true;
        }
        return i == s.size();
    }
};

Now let's look at the follow-up: now there are Billions of s. So we need to find a faster way than the above. One method is group and then binary search: group the index of the same kind of letter in t from small to high; then do a binary search to each letter in s. Or pre-processing t + binary search of s in t

See the code below:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> ids(26);//in the design, we can set ids as a private attribute
                                    //and can be initialized when instantiating one object
                                    //then call the
        for(int i=0; i<t.size(); ++i) {
            ids[t[i]-'a'].push_back(i);
        }
        int idx = -1;
        for(int i=0; i<s.size(); ++i) {
            int j = s[i] - 'a';
            auto it = upper_bound(ids[j].begin(), ids[j].end(), idx);//the first bigger than idx
            if(it == ids[j].end()) return false;
            idx = *it;
        }
        return true;
    }
};

Leetcode 727: Minimum Window Subsequence

https://leetcode.com/problems/minimum-window-subsequence/

Notes:

This question can be viewed as a follow up to Leetcode 76

The basic idea is to scan string s to match string t.

(1): when s[i] == t[j], both i and j update; otherwise, only i updates;

(2): when j == t.size(), meaning it is matched. Then we need to check back what is the minimum substring that fits the requirement.

(3): the method is scan back starting with position s[i]. Step(2) guarantees that T is subsequence of S[start ... i] ending with S[i], so we just need to do the reverse as the in Step (1). Once j is back to 0, meaning that it is found, then we can update the length.

(4): the update the i to i+1 (please note that i right now is already scanned back in Step 3.)

(5): repeat the above step util S is all scanned.

See the code below:

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.size(), n = T.size(), start = -1, minLen = INT_MAX, i = 0, j = 0;
        while (i < m) {
            if (S[i] == T[j]) {
                if (++j == n) {
                    int end = i + 1;
                    while (--j >= 0) {
                        while (S[i--] != T[j]);
                    }
                    ++i; ++j;//the above while loop runs 1 more backwards for both i and j
                    if (end - i < minLen) {
                        minLen = end - i;
                        start = i;
                    }
                }
            }
            ++i;
        }
        return (start != -1) ? S.substr(start, minLen) : "";
    }
};

There is another way to do it by applying dp:

dp[i][j] represents the initial position in S that S(dp[i][j], ... i) contains T as a subsequence.

The state transfer equation:

dp[i][j] = dp[i-1][j-1] when S[i] == T[j]
= dp[i-1][j] when S[i] != T[j]

If(dp[i][n] != -1) means there is fit. Then update the length.

See the code below:

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.size(), n = T.size(), start = -1, minLen = INT_MAX;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;//initialization
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= min(i, n); ++j) {
                dp[i][j] = (S[i - 1] == T[j - 1]) ? dp[i - 1][j - 1] : dp[i - 1][j];
            }
            if (dp[i][n] != -1) {
                int len = i - dp[i][n];
                if (minLen > len) {
                    minLen = len;
                    start = dp[i][n];
                }
            }
        }
        return (start != -1) ? S.substr(start, minLen) : "";
    }
};

Leetcode 76: Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/description/

Notes:

The basic idea is counting and comparing with a sliding window or two-pointer method.

One detail is how to compare? If we compare the counting arrays or hash table directly, it will be costly. One better way is we just need a counting variable to count the total number of valid letters.
See the code below:

class Solution {
public:
    string minWindow(string s, string t) {
        int len1 = s.size(), len2 = t.size();
        if(len1 < len2) return "";
        int start = 0, len = 0;
        vector v1(256, 0), v2(256, 0);
        for(auto &a : t) ++v2[a];
        int i = 0, j = 0, ct = 0;
        while(i < len1 && j < len1) {
            ++v1[s[j]];//move right pointer
            if(v1[s[j]] <= v2[s[j]]) ++ct;//only count when the letter is valid;
            if(ct == len2) {
                while(i < j && v2[s[i]] < v1[s[i]]) --v1[s[i++]];//move left pointer
                if(len == 0 || len > j - i + 1) {
                    len = j - i + 1;
                    start  = i;
                }
            }
            ++j;
        }
        return s.substr(start, len);
    }
};

Leetcode 395: Longest Substring with At Least K Repeating Characters

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/

Solution 1: Brute Force

If we fix the left and gradually extend the right, then it is easy to prove that there are N + (N-1) + ... + 2 + 1 = N(N+1)/2 substrings. For each substring, we can scan them first and then determine whether it is valid or not. If yes, record the length for comparison, and save it if it is longer.

For determination whether each substring is valid or not, we can use a num_unique variable to record the counting situations. When a new letter is introduced, we update the num_unique by adding 1; when the count of one letter reaches to k, we update the num_unique by reducing 1. Thus, when num_unique = 0, it means all the letters satisfy the requirements: the counting is no less than k.

See the code below:

class Solution {
public:
    int longestSubstring(string s, int k) {
        int res = 0, len = s.size();
        if(s.size() < k) return res;
        if(k==1) return len;
        for(int left = 0; left < len; ++left) {
            vector ct(26, 0);
            int num_unique = 0;
            for(int right = left; right < len; ++right) {
                int idx = s[right] - 'a';
                ++ct[idx];
                if(ct[idx] == 1) ++num_unique;//add a new unique letter;
                if(ct[idx] == k) --num_unique;//reach k counts;
                if(num_unique == 0) res = max(res, right - left + 1);//when all letters reach or more than k counts;
            }
        }
        return res;
    }
};

So the time complexity is O(N^2) and space complexity is O(26) or O(1), are there better solutions in time complexity?

Solution 2: Recursion

Another way to think about this question is also straightforward: if we know the total number of one kind of letter is less than k for the whole string, then we can break the string into smaller strings at the positions of that kind of letter. This is one typical method in programming: break a question into a smaller similar questions, which is also called recursion.

See the code below:

class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.size() < k) return 0;
        vector<int> ct(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        int idx = 0;
        while(idx < s.size() && ct[s[idx]-'a'] && ct[s[idx]-'a'] >= k) ++idx;
        if(idx == s.size()) return s.size();
        int left = longestSubstring(s.substr(0, idx), k);
        int right = longestSubstring(s.substr(idx+1), k);
        return max(left, right);
    }
};

The time complexity of the above code is still O(N^2). And there is a O(N) solution, which can be found below.

Solution 3: Categorization and Counting

There is one additional implicit constrain to the questions: there are only at most 26 kinds of letter in total. So for the valid substrings, they must satisfy:

(1) the number of each kind of letter is larger or equal to k;

(2) the total kinds of letter is between 1 and 26.

So we can scan the string with the above two constrains using two-pointer method. Basically, we find all the substrings that fit the above two constrains, then then find the one with the longest length.

See the code below:

class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.size() < k) return 0;
        int res = 0;
        for(int h=1; h<=26; ++h) {
            int i=0, j=0, unique = 0, noLessK = 0;
            vector<int> cts(26, 0);
            while(j<s.size()) {
             //   cout<<j<<endl;
                int b = s[j] - 'a';//move right idx and count
                if(cts[b] == 0) ++unique;
                ++cts[b];
                if(cts[b] == k) ++noLessK;
                if(unique > h) {
                    while(unique > h) {//move left idx to decrease total kinds of letter
                        int a = s[i] - 'a';   
                        if(cts[a] == k) --noLessK;
                        --cts[a];
                        if(cts[a] == 0) --unique;
                        ++i;
                    }
                }
                if(unique == noLessK) res = max(res, j-i+1);//satisfy two constrains
                ++j;
            }
        }
        return res;
    }
};

The time complexity is O(26*N) or O(N).

Follow ups or similar questions:

(1): what is the longest substring that fits the question?

(2): what is the total number of such substring?