###### tags: BiWeekly Contest
# BiWeekly Contest 142

## [3330. Find the Original Typed String I](https://leetcode.com/problems/find-the-original-typed-string-i/) (<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 <= word.length <= 100</code></li>
<li><code>word</code> consists only of lowercase English letters.</li>
</ul>

### Solution

#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(n)$

程式碼:

class Solution {
public:
    int possibleStringCount(string word) {
        vector<int> StringDelayTime;
        int num = 0;
        for (int i = 1; i < word.size(); i++) {
            if (word[i] == word[i - 1]) {
                num++;
            } else {
                if (num > 0) {
                    StringDelayTime.push_back(num + 1);
                    num = 0;
                }
            }
        }
        if (num > 0) {
            StringDelayTime.push_back(num + 1);
        }

        int result = 0;
        for (auto& n : StringDelayTime) {
            result += n;
        }
        return result - StringDelayTime.size() + 1;
    }
};

## [3331. Find Subtree Sizes After Changes](https://leetcode.com/problems/find-subtree-sizes-after-changes/) (<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>n == parent.length == s.length</code></li>
<li><code>1 <= n <= 10⁵</code></li>
<li><code>0 <= parent[i] <= n - 1</code> for all <code>i >= 1</code></li>
<li><code>parent[0] == -1</code></li>
<li><code>parent</code> represents a valid tree.</li>
<li><code>s</code> consists only of lowercase English letters.</li>
</ul>

### Solution

#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(n)$

程式碼:

## [3332. Maximum Points Tourist Can Earn](https://leetcode.com/problems/maximum-points-tourist-can-earn/) (<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 <= n <= 200</code></li>
<li><code>1 <= k <= 200</code></li>
<li><code>n == travelScore.length == travelScore[i].length == stayScore[i].length</code></li>
<li><code>k == stayScore.length</code></li>
<li><code>1 <= stayScore[i][j] <= 100</code></li>
<li><code>0 <= travelScore[i][j] <= 100</code></li>
<li><code>travelScore[i][i] == 0</code></li>
</ul>

### Solution

#### 時間複雜度: $O(k \cdot n^2)$

#### 空間複雜度: $O(n)$

程式碼:

## [3333. Find the Original Typed String II](https://leetcode.com/problems/find-the-original-typed-string-ii/) (<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>1 <= word.length <= 5 * 10⁵</code></li>
<li><code>word</code> consists only of lowercase English letters.</li>
<li><code>1 <= k <= 2000</code></li>
</ul>

### Solution

#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(1)$

程式碼: