###### tags: `Weekly Contest`
# Weekly Contest 390

## [3090. Maximum Length Substring With Two Occurrences](https://leetcode.com/problems/maximum-length-substring-with-two-occurrences/) (<font color=#00B8A3>Easy</font>)

限制 :

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

### Solution
利用前後夾擊的方式算出最長的序列，有點類似 LCS ，但又不太像。
#### 時間複雜度: $O(n^2)$

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

程式碼:

class Solution {
public:
    int max_len_of_string(string str, int begin, int end)
    {
        map<char, int> record;
        for (int i = begin; i <= end; i++)
        {
            auto it = record.find(str[i]);
            if (it == record.end())
            {
                record[str[i]] = 0;
            }
            record.find(str[i])->second++;
            if (record.find(str[i])->second > 2)
            {
                return i;
            }
        }
        return end;
    }
    int maximumLengthSubstring(string s) {
        int max_num = 0;
        for (int i = 0; i < s.size(); i++)
        {
            max_num = max(max_num, max_len_of_string(s, i, s.size()) - i);
        }
        return max_num;
    }
};

## [3091. Apply Operations to Make Sum of Array Greater Than or Equal to k](https://leetcode.com/problems/apply-operations-to-make-sum-of-array-greater-than-or-equal-to-k/) (<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 <= k <= 10⁵</code></li>
</ul>

### Solution
計算 k 的平方根 sqrt_num。如果 k 是完全平方數，最小操作數為 sqrt_num + sqrt_num - 2。如果 k 接近完全平方數，則為 sqrt_num + sqrt_num - 1。其他情況下，操作數量為 sqrt_num + sqrt_num。

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

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

程式碼:

class Solution {
public:
    int minOperations(int k) {
        int sqrt_num = sqrt(k);
        if (sqrt_num * sqrt_num == k)
            return sqrt_num + sqrt_num - 2;
        else if ((sqrt_num + 1) * sqrt_num >= k) {
            return sqrt_num + sqrt_num - 1;
        } else
            return sqrt_num + sqrt_num;
    }
};

## [3092. Most Frequent IDs](https://leetcode.com/problems/most-frequent-ids/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 <= nums.length == freq.length <= 10⁵</code></li>
<li><code>1 <= nums[i] <= 10⁵</code></li>
<li><code>-10⁵ <= freq[i] <= 10⁵</code></li>
<li><code>freq[i] != 0</code></li>
<li><code>The input is generated such that the occurrences of an ID will not be negative in any step.</code></li>
</ul>
### Solution

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

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

程式碼:

## [4]()(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>10⁴</code></li>
</ul>
### Solution

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

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

程式碼: