Appearance
question:Given an unsorted array of integers `arr`, you need to remove elements such that the remaining elements are arranged in increasing order. Write a function `longest_increasing_subsequence_length` that returns the length of the longest subsequence of `arr` which is strictly increasing. A subsequence can be derived from `arr` by deleting some or no elements without changing the order of the remaining elements. The function should have the following signature: ```python def longest_increasing_subsequence_length(arr: List[int]) -> int: ``` For example: - If `arr = [10, 9, 2, 5, 3, 7, 101, 18]`, the function should return `4` (the longest increasing subsequence is `[2, 3, 7, 101]`). - If `arr = [0, 1, 0, 3, 2, 3]`, the function should return `4` (the longest increasing subsequence is `[0, 1, 2, 3]`). - If `arr = [7, 7, 7, 7, 7, 7, 7]`, the function should return `1` (the longest increasing subsequence is `[7]`).
answer:from typing import List def longest_increasing_subsequence_length(arr: List[int]) -> int: if not arr: return 0 n = len(arr) lis = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j]: lis[i] = max(lis[i], lis[j] + 1) return max(lis)
question:Given a string `s` containing only lowercase letters, return the number of substrings that contain exactly 3 unique characters. For example, given s = "abcabc", the output should be 4 (substrings: "abc", "bca", "cab", "abc"). If there are no such substrings, return 0.
answer:def count_substrings_with_3_unique_chars(s): Returns the number of substrings that contain exactly 3 unique characters. n = len(s) if n < 3: return 0 count = 0 for i in range(n - 2): unique_chars = set() for j in range(i, min(i + 3, n)): unique_chars.add(s[j]) if len(unique_chars) == 3 and j == i + 2: count += 1 break return count
question:Implement a function that takes in a string `s` consisting of only uppercase English letters. Determine and return the length of the longest substring that contains at most `k` distinct characters. For example, given the string `"ABACCC"` and `k = 2`, the longest substring with at most 2 distinct characters is `"ACCC"`, which has length `4`.
answer:def length_of_longest_substring_k_distinct(s, k): Determines the length of the longest substring that contains at most k distinct characters. Parameters: s (str): The input string consisting of only uppercase English letters. k (int): The maximum number of distinct characters allowed in the substring. Returns: int: The length of the longest substring with at most k distinct characters. if k == 0: return 0 n = len(s) if n == 0: return 0 left, right = 0, 0 char_count = {} max_length = 0 while right < n: right_char = s[right] if right_char in char_count: char_count[right_char] += 1 else: char_count[right_char] = 1 while len(char_count) > k: left_char = s[left] char_count[left_char] -= 1 if char_count[left_char] == 0: del char_count[left_char] left += 1 current_length = right - left + 1 max_length = max(max_length, current_length) right += 1 return max_length
question:Given a **0-indexed** integer array `numbers` and an integer `n`, return _the number of subarrays of_ `numbers` _such that the sum of the elements in each subarray is divisible by_ `n`.
answer:def subarrays_divisible_by_n(numbers, n): Returns the number of subarrays of `numbers` such that the sum of the elements in each subarray is divisible by `n`. count_map = {0: 1} prefix_sum = 0 count = 0 for num in numbers: prefix_sum += num remainder = prefix_sum % n # In case remainder is negative, make it positive if remainder < 0: remainder += n if remainder in count_map: count += count_map[remainder] count_map[remainder] += 1 else: count_map[remainder] = 1 return count