# 2023/02/05 Mock interview Candidate:louis
###### tags: `mock interview`
---

<font size= 4><center> **倒數計時** </center></font>
<iframe id="oak-embed" width="700" height="400" style="display: block; margin: 0px auto; border: 0px;" src="http://zbryikt.github.io/quick-timer"></iframe>

# 題目講解
//start time: 21:41
//end time: 21:46

s[i...j] s[x...y] i<j, j<x, x<y
"abcac" if substring containc 'c' => "abcac"
Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length.

s = "adefaddaccc"
=>output: ["e","f","ccc"]

all of the substring,
[
"adefaddaccc"
"adefadda",
"ef",
"e",
"f",
"ccc",
]

string, contains only lowercase
find the maximum non-empty substring s
meet the rule

1. substring not overlap
2. substring contain all c

maximum number of substrings
return substrings

s: "aabfbf"
=> output: ["aa", "bfbf"]

s: "aabfbfa"
output -> ["aabfbfa"]

1. "aabfbfa" 2. "bfbf"
output -> "bfbf"

# 作法講解
//time: 21:50

1. record each letter l position, r position

012345678910
"adefaddaccc"

a: [0,7]
c: [8,10]
d: [1,6]
e: [2,2]
f: [3,3]

[
(x) "adefaddaccc" -> "adefadda", "ccc"
"adefadda", -> [0,7]
(x) "ef", -> "e", "f"
"e", [2,2]
"f", [3,3]
"ccc", [8,10]
]

"defadd" -> not good [1,6], -> [0,7]

hint:
how many maximum number of substring
substring must follow above conditions.
at most 26

2. iterate the letters
each letter, we loop from [l, r] -> check the [l, r] doesn't have a smaller [l, r](other letter) in range(l~r)

l == letter's left position
substring is start from l -> good a(0)

3. sort, and calculate the maximum substring we can choose

time: 22:06
example: "abbaccd"
0123456
"abbaccd"
a:[0,3]
b:[1,2]
c:[4,5]
d:[6,6]

a, for i in range[0:3]
b -> not smaller then 0
after for loop
[l, r] -> [0,3]

b, for i in range[1:2]
[l, r] -> [1,2]

c:
[l,r] -> [4,5]
d:
[l,r] -> [6,6]

[[0,3],[1,2],[4,5],[6,6]] -> sort by right position
[1,5], [4,6], [4,5], [6,6]
len > len

<!-- [1,2] -> smallest length
[1,2], [0,2], [4,5], [6,6] -> sort by right, compare the maximum left first

[1,5], [4,6], [7,8] -> never happen
len > len -->

record the current index (right position)

[[1,2],[0,3],[4,5],[6,6]]
1,2
index
[1,2], [4,5], [6,6] -> ans

i=1, 0<2 continue
2,5,6

012345
"babaff"
a is in b, and b is in a.

[0,3],[4,5]

# coding
//time: 22:20

// TC: O(26n + 26log26), SC: (26)
vector<string> maximumString(string &s) {
    
    int n = s.size();
    vector<int> l(26, n), r(26, -1);
    for (int i = 0; i < n; ++i){
        int ch = s[i]-'a';
        l[ch] = min(l[ch], i);
        r[ch] = max(r[ch], i);                 
    }
    
    vector<pair<int, int>> seg;
    // each letter, find the lpos, rpos
    for (int i = 0; i < 26; ++i) {
        if (r[i] == -1) continue; // not set
        
        int bound = r[i];
        int left = l[i];
        for (int j = left; j <= bound; ++j) { // O(n)
            bound = max(bound, r[s[j]-'a']); // extend               left = min(left, l[s[j]-'a']); 
        }
        if (left == l[i]) {
            seg.push_back({l[i], bound});               
        }
    }                      
    
    sort(seg.begin(), seg.end(), [&](auto &a, auto &b) {
        return a.second < b.second;
    });
    
    vector<string> ans;
    int right_pos = -1;
    for (auto &[lpos, rpos]: seg) {
        if (right_pos == -1 || right_pos < lpos) {
            right_pos = rpos;                                       ans.push_back({s.substr(lpos, rpos-lpos+1)});
        }
    }
                                                
    return ans;                             
}         

# 完成
//time: 22: 30

# comment
https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/

舉出一個不錯的例子, 來發現相同數量的substring, 需要回傳 minimum length
一開始想的方向(記錄所有字元的 l..r 範圍 )是不錯的,

[[0,3],[1,2],[4,5],[6,6]] -> sort by right position
這個部分有點小卡住
在125行 忘記 no overlap的限制,