2025-03¶

Table of Contents¶

131. Palindrome Partitioning¶

LeetCode | LeetCode CH (Medium)
Tags: string, dynamic programming, backtracking

131. Palindrome Partitioning - Python Solution

from typing import List


# Backtracking
def partition(s: str) -> List[List[str]]:
    n = len(s)
    res, path = [], []

    def dfs(start):
        if start == n:
            res.append(path.copy())
            return

        for end in range(start, n):
            cur = s[start : end + 1]
            if cur == cur[::-1]:
                path.append(cur)
                dfs(end + 1)
                path.pop()

    dfs(0)

    return res


if __name__ == "__main__":
    print(partition("aab"))
    # [['a', 'a', 'b'], ['aa', 'b']]

132. Palindrome Partitioning II¶

LeetCode | LeetCode CH (Hard)
Tags: string, dynamic programming
教你一步步思考 DP：从记忆化搜索到递推（Python/Java/C++/Go）

132. Palindrome Partitioning II - Python Solution

from functools import cache


# Memoization
def minCutMemoization(s: str) -> int:
    @cache
    def is_palindrome(left, right):
        if left >= right:
            return True
        return s[left] == s[right] and is_palindrome(left + 1, right - 1)

    @cache
    def dfs(right):
        if is_palindrome(0, right):
            return 0
        res = float("inf")
        for left in range(1, right + 1):
            if is_palindrome(left, right):
                res = min(res, 1 + dfs(left - 1))
        return res

    return dfs(len(s) - 1)


# Tabulation
def minCutTabulation(s: str) -> int:
    n = len(s)
    is_palindrome = [[True] * n for _ in range(n)]

    for left in range(n - 2, -1, -1):
        for right in range(left + 1, n):
            is_palindrome[left][right] = (
                s[left] == s[right] and is_palindrome[left + 1][right - 1]
            )

    dp = [0 for _ in range(n)]

    for right, is_pal in enumerate(is_palindrome[0]):
        if is_pal:
            continue
        res = float("inf")
        for left in range(1, right + 1):
            if is_palindrome[left][right]:
                res = min(res, 1 + dp[left - 1])
        dp[right] = res

    return dp[-1]


s = "aab"
print(minCutMemoization(s))  # 1
print(minCutTabulation(s))  # 1

1278. Palindrome Partitioning III¶

LeetCode | LeetCode CH (Hard)
Tags: string, dynamic programming

1278. Palindrome Partitioning III - Python Solution

# DP
def palindromePartition(s: str, k: int) -> int:
    n = len(s)
    min_change = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            min_change[i][j] = min_change[i + 1][j - 1] + (
                1 if s[i] != s[j] else 0
            )

    dp = min_change[0]
    for i in range(1, k):
        for right in range(n - k + i, i - 1, -1):
            dp[right] = min(
                dp[left - 1] + min_change[left][right]
                for left in range(i, right + 1)
            )

    return dp[-1]


s = "aabbc"
k = 3
print(palindromePartition(s, k))  # 0

1745. Palindrome Partitioning IV¶

LeetCode | LeetCode CH (Hard)
Tags: string, dynamic programming

1745. Palindrome Partitioning IV - Python Solution

# DP
def checkPartitioning(s: str) -> bool:
    def palidrome_partition(s, k):
        n = len(s)
        min_change = [[0] * n for _ in range(n)]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                min_change[i][j] = min_change[i + 1][j - 1] + (
                    1 if s[i] != s[j] else 0
                )

        dp = min_change[0]

        for i in range(1, k):
            for right in range(n - k + i, i - 1, -1):
                dp[right] = min(
                    dp[left - 1] + min_change[left][right]
                    for left in range(i, right + 1)
                )

        return dp[-1]

    return palidrome_partition(s, 3) == 0


s = "abcbdd"
print(checkPartitioning(s))  # True

1328. Break a Palindrome¶

LeetCode | LeetCode CH (Medium)
Tags: string, greedy

1328. Break a Palindrome - Python Solution

# Greedy
def breakPalindrome(palindrome: str) -> str:
    n = len(palindrome)
    if n == 1:
        return ""

    for i in range(n // 2):
        if palindrome[i] != "a":
            return palindrome[:i] + "a" + palindrome[i + 1 :]

    return palindrome[:-1] + "b"


palindrome = "abccba"
print(breakPalindrome(palindrome))  # "aaccba"

2588. Count the Number of Beautiful Subarrays¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, bit manipulation, prefix sum
nums = [4, 3, 1, 2, 4]
In bianry

4 -> 100
3 -> 011
1 -> 001
2 -> 010
4 -> 100

2588. Count the Number of Beautiful Subarrays - Python Solution

from collections import defaultdict
from typing import List


def beautifulSubarrays(nums: List[int]) -> int:
    res, s = 0, 0
    cnt = defaultdict(int)
    cnt[0] = 1

    for x in nums:
        s ^= x
        res += cnt[s]
        cnt[s] += 1

    return res


nums = [4, 3, 1, 2, 4]
print(beautifulSubarrays(nums))  # 2

2597. The Number of Beautiful Subsets¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, math, dynamic programming, backtracking, sorting, combinatorics

2597. The Number of Beautiful Subsets - C++ Solution

#include <functional>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
   public:
    int beautifulSubsets(vector<int>& nums, int k) {
        int res = 0;
        unordered_map<int, int> cnt;

        auto dfs = [&](auto&& self, int i) -> void {
            if (i == (int)nums.size()) {
                res++;
                return;
            }
            self(self, i + 1);  // Skip nums[i]
            int x = nums[i];
            if (cnt[x - k] == 0 && cnt[x + k] == 0) {
                cnt[x]++;
                self(self, i + 1);  // Include nums[i]
                cnt[x]--;           // Backtrack
            }
        };

        dfs(dfs, 0);

        return res - 1;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3, 4};
    int k = 1;
    cout << sol.beautifulSubsets(nums, k) << endl;
    return 0;
}

2234. Maximum Total Beauty of the Gardens¶

LeetCode | LeetCode CH (Hard)
Tags: array, two pointers, binary search, greedy, sorting

2234. Maximum Total Beauty of the Gardens - C++ Solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target,
                        int full, int partial) {
    int n = flowers.size();

    long long left = newFlowers - 1LL * target * n;
    for (int& flower : flowers) {
        flower = min(flower, target);
        left += flower;
    }

    if (left == newFlowers) return 1LL * full * n;

    if (left >= 0) {
        return max(1LL * (target - 1) * partial + 1LL * (n - 1) * full,
                   1LL * n * full);
    }

    sort(flowers.begin(), flowers.end());
    long long res = 0, pre_sum = 0;

    int j = 0;
    for (int i = 1; i <= n; i++) {
        left += target - flowers[i - 1];
        if (left < 0) {
            continue;
        }

        while (j < i && 1LL * flowers[j] * j <= pre_sum + left) {
            pre_sum += flowers[j];
            j++;
        }

        long long avg = (left + pre_sum) / j;
        long long total_beauty = avg * partial + 1LL * (n - i) * full;
        res = max(res, total_beauty);
    }

    return res;
}

int main() {
    vector<int> flowers = {1, 3, 1, 1};
    long long newFlowers = 7;
    int target = 6;
    int full = 12;
    int partial = 1;
    long long res = maximumBeauty(flowers, newFlowers, target, full, partial);
    cout << res << endl;  // 14
    return 0;
}

2070. Most Beautiful Item for Each Query¶

LeetCode | LeetCode CH (Medium)
Tags: array, binary search, sorting

2070. Most Beautiful Item for Each Query - C++ Solution

#include <algorithm>
#include <iostream>
#include <numeric>
#include <ranges>
#include <vector>
using namespace std;

vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
    ranges::sort(items, {}, [](auto& item) { return item[0]; });
    vector<int> idx(queries.size());
    iota(idx.begin(), idx.end(), 0);
    ranges::sort(idx, {}, [&](int i) { return queries[i]; });

    vector<int> res(queries.size());
    int max_beauty = 0, j = 0;
    for (int i : idx) {
        int q = queries[i];
        while (j < items.size() && items[j][0] <= q) {
            max_beauty = max(max_beauty, items[j][1]);
            j++;
        }
        res[i] = max_beauty;
    }
    return res;
}

int main() {
    vector<vector<int>> items = {{1, 2}, {2, 4}, {3, 2}, {5, 6}, {3, 5}};
    vector<int> queries = {1, 2, 3, 4, 5, 6};
    vector<int> res = maximumBeauty(items, queries);
    // 2 4 5 5 6 6
    for (int i : res) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

2269. Find the K-Beauty of a Number¶

LeetCode | LeetCode CH (Easy)
Tags: math, string, sliding window

2269. Find the K-Beauty of a Number - Python Solution

def divisorSubstrings(num: int, k: int) -> int:
    numStr = str(num)
    n = len(numStr)
    res = 0

    for i in range(n - k + 1):
        x = int(numStr[i : i + k])
        if x > 0 and num % x == 0:
            res += 1

    return res


num = 240
k = 2
print(divisorSubstrings(num, k))  # 2

2012. Sum of Beauty in the Array¶

LeetCode | LeetCode CH (Medium)
Tags: array

2012. Sum of Beauty in the Array - Python Solution

from typing import List


# DP Prefix and Suffix Decomposition
def sumOfBeauties(nums: List[int]) -> int:
    n = len(nums)
    suf_min = [0] * n
    suf_min[n - 1] = nums[n - 1]
    for i in range(n - 2, 1, -1):
        suf_min[i] = min(suf_min[i + 1], nums[i])

    res = 0
    pre_max = nums[0]
    for i in range(1, n - 1):
        x = nums[i]
        if pre_max < x < suf_min[i + 1]:
            res += 2
        elif nums[i - 1] < x < nums[i + 1]:
            res += 1
        pre_max = max(pre_max, x)

    return res


nums = [2, 4, 6, 4, 5]
print(sumOfBeauties(nums))  # 1

3305. Count of Substrings Containing Every Vowel and K Consonants I¶

LeetCode | LeetCode CH (Medium)
Tags: hash table, string, sliding window

3305. Count of Substrings Containing Every Vowel and K Consonants I - Python Solution

from collections import defaultdict


# Sliding Window Variable Subarrays Exact
def countOfSubstrings(word: str, k: int) -> int:
    vowels = {"a", "e", "i", "o", "u"}
    n = len(word)

    def count(m: int) -> int:
        occur = defaultdict(int)
        valid_vow_cnt, con_cnt = 0, 0
        left = 0
        res = 0

        for right in range(n):
            while left < n and (con_cnt < m or valid_vow_cnt < 5):
                if word[left] in vowels:
                    if occur[word[left]] == 0:
                        valid_vow_cnt += 1
                    occur[word[left]] += 1
                else:
                    con_cnt += 1
                left += 1

            if con_cnt >= m and valid_vow_cnt == 5:
                res += n - left + 1

            if word[right] in vowels:
                occur[word[right]] -= 1
                if occur[word[right]] == 0:
                    valid_vow_cnt -= 1
            else:
                con_cnt -= 1

        return res

    return count(k) - count(k + 1)


word = "ieaouqqieaouqq"
k = 1
print(countOfSubstrings(word, k))  # 3

3306. Count of Substrings Containing Every Vowel and K Consonants II¶

LeetCode | LeetCode CH (Medium)
Tags: hash table, string, sliding window

3306. Count of Substrings Containing Every Vowel and K Consonants II - Python Solution

from collections import defaultdict


# Sliding Window Variable Subarrays Exact
def countOfSubstrings(word: str, k: int) -> int:
    vowels = {"a", "e", "i", "o", "u"}
    n = len(word)

    def count(m: int) -> int:
        occur = defaultdict(int)
        valid_vow_cnt, con_cnt = 0, 0
        left = 0
        res = 0

        for right in range(n):
            while left < n and (con_cnt < m or valid_vow_cnt < 5):
                if word[left] in vowels:
                    if occur[word[left]] == 0:
                        valid_vow_cnt += 1
                    occur[word[left]] += 1
                else:
                    con_cnt += 1
                left += 1

            if con_cnt >= m and valid_vow_cnt == 5:
                res += n - left + 1

            if word[right] in vowels:
                occur[word[right]] -= 1
                if occur[word[right]] == 0:
                    valid_vow_cnt -= 1
            else:
                con_cnt -= 1

        return res

    return count(k) - count(k + 1)


word = "ieaouqqieaouqq"
k = 1
print(countOfSubstrings(word, k))  # 3

3340. Check Balanced String¶

LeetCode | LeetCode CH (Easy)
Tags: string

3340. Check Balanced String - Python Solution

def isBalanced1(num: str) -> bool:
    nums = [int(c) for c in num]
    odd = nums[::2]
    even = nums[1::2]

    return sum(odd) == sum(even)


def isBalanced2(num: str) -> bool:
    cur = 0
    n = len(num)

    for i in range(0, n, 2):
        cur += int(num[i])

    for i in range(1, n, 2):
        cur -= int(num[i])

    return cur == 0


if __name__ == "__main__":
    print(isBalanced1("1234"))  # False
    print(isBalanced1("24123"))  # True
    print(isBalanced2("1234"))  # False
    print(isBalanced2("24123"))  # True

3110. Score of a String¶

LeetCode | LeetCode CH (Easy)
Tags: string

3110. Score of a String - Python Solution

# Traversal
def scoreOfString(s: str) -> int:
    res = 0

    for i in range(1, len(s)):
        res += abs(ord(s[i]) - ord(s[i - 1]))

    return res


if __name__ == "__main__":
    print(scoreOfString("hello"))  # 13

2272. Substring With Largest Variance¶

LeetCode | LeetCode CH (Hard)
Tags: array, dynamic programming

2272. Substring With Largest Variance - Python Solution

from itertools import permutations
from math import inf
from string import ascii_lowercase


# DP State Machine
def largestVariance(s: str) -> int:
    res = 0

    for a, b in permutations(ascii_lowercase, 2):
        f0, f1 = 0, -inf
        for ch in s:
            if ch == a:
                f0 = max(f0, 0) + 1
                f1 += 1
            elif ch == b:
                f1 = f0 = max(f0, 0) - 1

            res = max(res, f1)
    return res


if __name__ == "__main__":
    s = "aababbb"
    print(largestVariance(s))  # 3

1963. Minimum Number of Swaps to Make the String Balanced¶

LeetCode | LeetCode CH (Medium)
Tags: two pointers, string, stack, greedy

1963. Minimum Number of Swaps to Make the String Balanced - Python Solution

def minSwaps(s: str) -> int:
    res, balance = 0, 0

    for char in s:
        if char == "[":
            balance += 1
        elif balance > 0:
            balance -= 1
        else:
            res += 1
            balance += 1

    return res


if __name__ == "__main__":
    print(minSwaps("][]["))  # 1
    print(minSwaps("]]][[["))  # 2

2614. Prime In Diagonal¶

LeetCode | LeetCode CH (Easy)
Tags: array, math, matrix, number theory

2614. Prime In Diagonal - Python Solution

from math import isqrt
from typing import List


# Prime
def diagonalPrime(nums: List[List[int]]) -> int:
    def is_prime(n):
        if n <= 1:
            return False

        for i in range(2, isqrt(n) + 1):
            if n % i == 0:
                return False
        return True

    res = 0
    for i, row in enumerate(nums):
        for x in row[i], row[-1 - i]:
            if x > res and is_prime(x):
                res = x

    return res


if __name__ == "__main__":
    nums = [[1, 2, 3], [5, 6, 7], [9, 10, 11]]
    print(diagonalPrime(nums))  # 11

2610. Convert an Array Into a 2D Array With Conditions¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table

2610. Convert an Array Into a 2D Array With Conditions - Python Solution

from collections import Counter
from typing import List


def findMatrix(nums: List[int]) -> List[List[int]]:
    counts = Counter(nums)
    res = []

    for num, freq in counts.items():
        while len(res) < freq:
            res.append([])

        for i in range(freq):
            res[i].append(num)

    return res


if __name__ == "__main__":
    nums = [1, 3, 4, 1, 2, 3, 1]
    print(findMatrix(nums))
    # [[1, 3, 4, 2], [1, 3], [1]]

2612. Minimum Reverse Operations¶

LeetCode | LeetCode CH (Hard)
Tags: array, breadth first search, ordered set

2612. Minimum Reverse Operations - Python Solution

from collections import deque
from typing import List


class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))

    def find(self, n: int) -> int:
        if self.parent[n] != n:
            self.parent[n] = self.find(self.parent[n])
        return self.parent[n]

    def union(self, n1: int, n2: int) -> None:
        self.parent[self.find(n1)] = self.find(n2)


def minReverseOperations(
    n: int, p: int, banned: List[int], k: int
) -> List[int]:
    indices = UnionFind(n + 2)
    indices.union(p, p + 2)

    for i in banned:
        indices.union(i, i + 2)

    res = [-1] * n
    res[p] = 0
    q = deque([p])

    while q:
        i = q.popleft()
        mn = max(i - k + 1, k - i - 1)
        mx = min(i + k - 1, n * 2 - k - i - 1)
        j = indices.find(mn)
        while j <= mx:
            res[j] = res[i] + 1
            q.append(j)
            indices.union(j, mx + 2)
            j = indices.find(j + 2)

    return res


if __name__ == "__main__":
    n = 4
    p = 0
    banned = [1, 2]
    k = 4
    print(minReverseOperations(n, p, banned, k))
    # [0, -1, -1, 1]

2680. Maximum OR¶

LeetCode | LeetCode CH (Medium)
Tags: array, greedy, bit manipulation, prefix sum

2680. Maximum OR - Python Solution

from typing import List


# Greedy
def maximumOr(nums: List[int], k: int) -> int:
    """Maximum OR of Array After k Operations

    Args:
        nums (List[int]): provided list of integers
        k (int): number of operations

    Returns:
        int: maximum OR of array after k operations
    """
    n = len(nums)
    suffix = [0 for _ in range(n)]

    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] | nums[i + 1]

    res, pre = 0, 0
    for num, suf in zip(nums, suffix):
        res = max(res, pre | (num << k) | suf)
        pre |= num

    return res


if __name__ == "__main__":
    print(maximumOr(nums=[8, 1, 2], k=2))  # 35

2643. Row With Maximum Ones¶

LeetCode | LeetCode CH (Easy)
Tags: array, matrix

2643. Row With Maximum Ones - Python Solution

from typing import List


def rowAndMaximumOnes(mat: List[List[int]]) -> List[int]:
    """Return the index of the row with the maximum number of ones."""
    res = [0, 0]
    for i, row in enumerate(mat):
        cnt = sum(row)
        if cnt > res[1]:
            res[0], res[1] = i, cnt

    return res


if __name__ == "__main__":
    mat = [[0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0]]
    print(rowAndMaximumOnes(mat))  # [2, 4]

2643. Row With Maximum Ones - C++ Solution

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
    vector<int> res = {0, 0};

    for (size_t i = 0; i < mat.size(); i++) {
        int cnt = accumulate(mat[i].begin(), mat[i].end(), 0);
        if (cnt > res[1]) {
            res[0] = (int)i;
            res[1] = cnt;
        }
    }
    return res;
}

int main() {
    vector<vector<int>> mat = {
        {0, 0, 0, 1}, {0, 1, 1, 1}, {1, 1, 1, 1}, {0, 0, 0, 0}};
    vector<int> res = rowAndMaximumOnes(mat);
    cout << res[0] << ", " << res[1] << endl;  // 2, 4
    return 0;
}

2116. Check if a Parentheses String Can Be Valid¶

LeetCode | LeetCode CH (Medium)
Tags: string, stack, greedy

2116. Check if a Parentheses String Can Be Valid - Python Solution

# Valid Parentheses Strings
def canBeValid(s: str, locked: str) -> bool:
    if len(s) % 2:
        return False

    mx, mn = 0, 0
    for ch, lock in zip(s, locked):
        if lock == "1":
            d = 1 if ch == "(" else -1
            mx += d
            if mx < 0:
                return False
            mn += d
        else:
            mx += 1
            mn -= 1

        if mn < 0:
            mn = 1

    return mn == 0


if __name__ == "__main__":
    s = "))()))"
    locked = "010100"
    print(canBeValid(s, locked))  # True

2116. Check if a Parentheses String Can Be Valid - C++ Solution

#include <iostream>
#include <string>
using namespace std;

// Valid Parentheses Strings
bool canBeValid(string s, string locked) {
    if (s.length() % 2 != 0) {
        return false;
    }

    int mx = 0, mn = 0;
    for (size_t i = 0; i < s.length(); ++i) {
        char ch = s[i];
        char lock = locked[i];

        if (lock == '1') {
            int d = (ch == '(') ? 1 : -1;
            mx += d;
            if (mx < 0) {
                return false;
            }
            mn += d;
        } else {
            mx += 1;
            mn -= 1;
        }

        if (mn < 0) {
            mn = 1;
        }
    }

    return mn == 0;
}

int main() {
    string s = "))()))";
    string locked = "010100";
    cout << (canBeValid(s, locked) ? "true" : "false") << endl;  // true
    return 0;
}

2255. Count Prefixes of a Given String¶

LeetCode | LeetCode CH (Easy)
Tags: array, string

2255. Count Prefixes of a Given String - Python Solution

from typing import List


def countPrefixes(words: List[str], s: str) -> int:
    res = 0
    for word in words:
        if s.startswith(word):
            res += 1
    return res


if __name__ == "__main__":
    words = ["a", "b", "c", "ab", "bc", "abc"]
    s = "abc"
    print(countPrefixes(words, s))  # 3

2711. Difference of Number of Distinct Values on Diagonals¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, matrix

2711. Difference of Number of Distinct Values on Diagonals - Python Solution

from typing import List


def differenceOfDistinctValues(grid: List[List[int]]) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    res = [[0] * n for _ in range(m)]
    st = set()

    for k in range(1, m + n):
        min_j = max(n - k, 0)
        max_j = min(m + n - 1 - k, n - 1)

        st.clear()
        for j in range(min_j, max_j + 1):
            i = k + j - n
            res[i][j] = len(st)
            st.add(grid[i][j])

        st.clear()
        for j in range(max_j, min_j - 1, -1):
            i = k + j - n
            res[i][j] = abs(res[i][j] - len(st))
            st.add(grid[i][j])

    return res


if __name__ == "__main__":
    grid = [[1, 2, 3], [3, 1, 5], [3, 2, 1]]
    print(differenceOfDistinctValues(grid))
    # [[1, 1, 0], [1, 0, 1], [0, 1, 1]]

2829. Determine the Minimum Sum of a k-avoiding Array¶

LeetCode | LeetCode CH (Medium)
Tags: math, greedy

2829. Determine the Minimum Sum of a k-avoiding Array - Python Solution

def minimumSum(n: int, k: int) -> int:
    m = min(k // 2, n)
    return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2


if __name__ == "__main__":
    n = 5
    k = 4
    print(minimumSum(n, k))  # 18

2712. Minimum Cost to Make All Characters Equal¶

LeetCode | LeetCode CH (Medium)
Tags: string, dynamic programming, greedy

2712. Minimum Cost to Make All Characters Equal - Python Solution

def minimumCost(s: str) -> int:
    n = len(s)
    res = 0
    for i in range(1, n):
        if s[i - 1] != s[i]:
            res += min(i, n - i)

    return res


if __name__ == "__main__":
    s = "0011"
    print(minimumCost(s))  # 2

2716. Minimize String Length¶

LeetCode | LeetCode CH (Easy)
Tags: hash table, string

2716. Minimize String Length - Python Solution

def minimizedStringLength(s: str) -> int:
    return len(set(s))


if __name__ == "__main__":
    s = "aaabc"
    print(minimizedStringLength(s))  # 3

2360. Longest Cycle in a Graph¶

LeetCode | LeetCode CH (Hard)
Tags: depth first search, breadth first search, graph, topological sort

2360. Longest Cycle in a Graph - Python Solution

from typing import List


def longestCycle(edges: List[int]) -> int:
    n = len(edges)
    res = -1
    cur = 1
    vis = [0 for _ in range(n)]

    for i in range(n):
        start = cur
        while i != -1 and vis[i] == 0:
            vis[i] = cur
            cur += 1
            i = edges[i]
        if i != -1 and vis[i] >= start:
            res = max(res, cur - vis[i])

    return res


if __name__ == "__main__":
    edges = [3, 3, 4, 2, 3]
    print(longestCycle(edges))  # 3

2109. Adding Spaces to a String¶

LeetCode | LeetCode CH (Medium)
Tags: array, two pointers, string, simulation

2109. Adding Spaces to a String - Python Solution

from typing import List


def addSpaces(s: str, spaces: List[int]) -> str:
    res = []
    spaces.sort()
    n = len(spaces)
    j = 0

    for i, ch in enumerate(s):
        if j < n and i == spaces[j]:
            res.append(" ")
            j += 1
        res.append(ch)

    return "".join(res)


if __name__ == "__main__":
    s = "LeetcodeHelpsMeLearn"
    spaces = [8, 13, 15]
    print(addSpaces(s, spaces))  # Leetcode Helps Me Learn

2278. Percentage of Letter in String¶

LeetCode | LeetCode CH (Easy)
Tags: string

2278. Percentage of Letter in String - Python Solution

from collections import Counter


def percentageLetter(s: str, letter: str) -> int:
    cnt = Counter(s)
    n = len(s)

    if letter in cnt.keys():
        return int(cnt[letter] / n * 100)

    return 0


if __name__ == "__main__":
    s = "foobar"
    letter = "o"
    print(percentageLetter(s, letter))  # 33