---
# System prepended metadata

title: '2023/02/05 Mock interview Candidate:louis'
tags: [mock interview]

---

# 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

```cpp=

// 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的限制, 
