Blind 75

The problem There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity. ...

The Problem Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: [4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time. ...

The Problem Given a string s containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every closing bracket has a corresponding open bracket of the same type. Examples Input: s = "()" Output: true Input: s = "()[]{}" Output: true Input: s = "(]" Output: false Input: s = "([])" Output: true Constraints 1 <= s.length <= 10⁴ s consists of parentheses only '()[]{}'. Brute Force Solution func isValid(_ s: String) -> Bool { var s = s while s.contains("()") || s.contains("{}") || s.contains("[]") { s = s.replacingOccurrences(of: "()", with: "") s = s.replacingOccurrences(of: "{}", with: "") s = s.replacingOccurrences(of: "[]", with: "") } return s.isEmpty } Explanation The brute force way to solve this problem is to check if the string contains "()", "{}", "[]" and replace them with an empty string. It’s not a very efficient algorithm and takes O(n²) time because of the while loop and the replacing operation on the entire string. We can optimize it by using a stack data structure. ...

The Problem Given two strings s and t of lengths m and n, respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". A substring is a contiguous, non-empty sequence of characters within a string. The test cases will be generated such that the answer is unique. Examples Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window. Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return an empty string. Constraints m == s.length n == t.length 1 <= m, n <= 10⁵ s and t consist of uppercase and lowercase English letters. Follow-up: Could you find an algorithm that runs in O(m + n) time? ...

The problem You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations. Examples Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. There may exist other ways to achieve this answer too. Constraints 1 <= s.length <= 105 s consists of only uppercase English letters. 0 <= k <= s.length Brute force solution func characterReplacement(_ s: String, _ k: Int) -> Int { let n = s.count let s = Array(s) var res = 0 for i in 0 ..< n { var count: [Character: Int] = [:] var maxF = 0 for j in i ..< n { count[s[j], default: 0] += 1 maxF = max(maxF, count[s[j]]!) let windowSize = (j - i + 1) let numOfCharsToReplace = (windowSize - maxF) let canReplace = (numOfCharsToReplace <= k) if canReplace { res = max(res, windowSize) } } } return res } Explanation First things first, we need to figure out which character we are going to replace. We can do this by using a dictionary. This way, we can calculate the most frequent character in the substring. After that, we will be able to calculate the number of characters to replace and check if we can replace the character. This algorithm is not very fast and takes O(n^2) time. We can improve it further and optimize it to achieve O(n) time complexity. ...