Leetcode

443. String Compression Given an array of characters chars, compress it using the following algorithm: Begin with an empty string s. For each group of consecutive repeating characters in chars: If the group’s length is 1, append the character to s. Otherwise, append the character followed by the group’s length. The compressed string s should not be returned separately, but instead be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars. ...

1207. Unique Number of Occurrences Given an array of integers arr, write a function that returns true if and only if the number of occurrences of each value in the array is unique. Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences. Example 2: Input: arr = [1,2] Output: false Example 3: Input: arr = [-3,0,1,-3,1,1,1,-3,10,0] Output: true Constraints: ...

1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence Given a sentence that consists of some words separated by a single space, and a searchWord. You have to check if searchWord is a prefix of any word in sentence. Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed). If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1. ...

1844. Replace All Digits with Characters You are given a 0-indexed string s that has lowercase English letters in its even indices and digits in its odd indices. There is a function shift(c, x), where c is a character and x is a digit, that returns the xth character after c. For example, shift(‘a’, 5) = ‘f’ and shift(‘x’, 0) = ‘x’. For every odd index i, you want to replace the digit s[i] with shift(s[i-1], s[i]). ...

1845. Seat Reservation Manager Design a system that manages the reservation state of n seats that are numbered from 1 to n. Implement the SeatManager class: SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available. int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number. void unreserve(int seatNumber) Unreserves the seat with the given seatNumber. Example 1: Input ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"] [[5], [], [], [2], [], [], [], [], [5]] Output [null, 1, 2, null, 2, 3, 4, 5, null] Explanation SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5]. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3. seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4. seatManager.reserve(); // The only available seat is seat 5, so return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5]. ...

1846. Maximum Element After Decreasing and Rearranging You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions: The value of the first element in arr must be 1. The absolute difference between any 2 adjacent elements must be less than or equal to 1. In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x. There are 2 types of operations that you can perform any number of times: ...

859. Buddy Strings Given two strings a and b, return true if you can swap two letters in a so the result is equal to b, otherwise, return false. Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at a[i] and a[j]. For example, swapping at indices 0 and 2 in “abcd” results in “cbad”. Example 1: Input: a = "ab", b = "ba" Output: true Explanation: You can swap a[0] = 'a' and a[1] = 'b' to get "ba", which is equal to b. Example 2: Input: a = "ab", b = "ab" Output: false Explanation: The only letters you can swap are a[0] = 'a' and a[1] = 'b', which results in "ba" != b. Example 3: Input: a = "aa", b = "aa" Output: true Explanation: You can swap a[0] = 'a' and a[1] = 'a' to get "aa", which is equal to b. Example 4: Input: a = "aaaaaaabc", b = "aaaaaaacb" Output: true Constraints: ...

98. Validate Binary Search Tree Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. Example 1: Input: root = [2,1,3] Output: true ...

211. Design Add and Search Words Data Structure Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure, it can be matched later. bool search(word) Returns true if there is any string in the data structure that - matches word or false otherwise. word may contain dots ‘.’ where dots can be matched with any letter. Example: Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True Constraints: ...

72. Edit Distance Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') Constraints: ...