Tyson's blog

QuestionLeetCode Link | 459. Repeated Substring Pattern | Easy Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. Constrains 1 <= s.length <= 10^4 s consists of lowercase English letters. ExamplesExample 1 Input: s = “abab”Output: trueExplanation: It is the substring “ab” twice. Example 2 Input: s = “aba”Output: false Example 3 Input: s = “abcabcabcabc”Output: trueExplanation: It is the sub ...

QuestionLeetCode Link | 28. Find the Index of the First Occurrence in a String | Easy Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Constrains 1 <= haystack.length, needle.length <= 10^4 haystack and needle consist of only lowercase English characters. ExamplesExample 1 Input: haystack = “sadbutsad”, needle = “sad”Output: 0Explanation: “sad” occurs at index 0 and 6.The first occurre ...

What is KMP?The Knuth-Morris-Pratt (KMP) algorithm is a string matching algorithm designed for searching substrings or patterns within a main text string efficiently. It was developed by Donald Knuth, Vaughan Pratt, and James H. Morris in 1977 (where thses three names appears on the algorithm name). The key advantage of the KMP algorithm over naive substring search methods is its linear time complexity, which makes it much more efficient, especially when dealing with large texts or patterns. Eff ...

QuestionLeetCode Link | 151. Reverse Words In a String | Medium Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space. Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra ...

QuestionLeetCode Link | 541. Reverse String II | Easy Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string. If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original. Constrains 1 <= s.length <= 10^4 s consists of only lowercase English letters. 1 <= k <= 10^4 Examples ...

QuestionLeetCode Link | 344. Reverse String | Easy Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory. Constrains 1 <= s.length <= 10^5 s[i] is a printable ascii character. ExamplesExample 1 Input: s = [“h”,”e”,”l”,”l”,”o”]Output: [“o”,”l”,”l”,”e”,”h”] Example 2 Input: s = [“H”,”a”,”n”,”n”,”a”,”h”]Output: [“h”,”a”,”n”,”n”,”a”,”H”] Solution ApproachMethod: ...

QuestionLeetCode Link | 18. Four Sum | Medium Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order. Constrains 1 <= nums.length <= 200 -10^9 <= nums[i] <= 10^9 -10^9 <= target <= 10^9 ExamplesExample 1 Input: nums = [1,0,-1,0,-2,2], target = 0Output: ...

QuestionLeetCode Link | 15. Three Sum | Medium 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. Constrains 3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5 ExamplesExample 1 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 ...

QuestionLeetCode Link | 383. Ransom Note | Easy Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote. Constrains 1 <= ransomNote.length, magazine.length <= 10^5 ransomNote and magazine consist of lowercase English letters. ExamplesExample 1 Input: ransomNote = “a”, magazine = “b”Output: false Example 2 Input: ransomNote = “a ...

QuestionLeetCode Link | 454. Four Sum II | Medium Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that: 0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 Constrains n == nums1.length n == nums2.length n == nums3.length n == nums4.length 1 <= n <= 200 -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28 ExamplesExample 1 Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1 ...