Swift

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. ...

The Problem Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous non-empty sequence of characters within a string. Examples Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring. "pwke" is a subsequence and not a substring. Constraints 0 <= s.length <= 5 * 10⁴ s consists of English letters, digits, symbols, and spaces. Brute Force Solution func lengthOfLongestSubstring(_ s: String) -> Int { let n = s.count var res = 0 for i in 0 ..< n { var chars: [Character] = [] for j in i ..< n { if chars.contains(s[j]) { break } chars.append(s[j]) } res = max(res, chars.count) } return res } Explanation Let’s start by visualizing the problem: ...

The problem You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Examples Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0. Constraints 1 <= prices.length <= 10⁵ 0 <= prices[i] <= 10⁴ Brute force solution func maxProfit(_ prices: [Int]) -> Int { let n = prices.count var res = 0 for i in 0 ..< n { for j in i + 1 ..< n { let profit = prices[j] - prices[i] if profit > 0 { res = max(res, profit) } } } return res } Explanation We can start with a brute force solution and find a way to a more optimal solution as we go. By visualizing the problem using input from example 1 [7,1,5,3,6,4]: ...

The Problem You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that, together with the x-axis, form a container such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. ...

The Problem Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Examples Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter. Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0. Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0. Constraints 3 <= nums.length <= 3000 -10⁵ <= nums[i] <= 10⁵ Brute Force Solution func threeSum(_ nums: [Int]) -> [[Int]] { var nums = nums let n = nums.count var res: Set<[Int]> = [] nums.sort() for i in 0 ..< n { for j in i + 1 ..< n { for k in j + 1 ..< n { if nums[i] + nums[j] + nums[k] == 0 { let val = [nums[i], nums[j], nums[k]] res.insert(val) } } } } return Array(res) } Explanation Let’s start with the brute force solution. According to the problem, we need to find triplet elements that, when added together, equal 0. By looking at examples, the first thing that comes to mind is to use three loops, add each of the elements, and compare the result with 0. If the result equals 0, we add the elements to the result. ...