Reverse Words in a String Iii

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1 Input: "Let's take LeetCode contest" Output: "s'teL ekat edoCteeL tsetnoc" Note In the string, each word is separated by single space and there will not be any extra space in the string. Solution class Solution: def reverseWords(self, s: str) -> str: N = len(s) start = 0 s = list(s) res = "" while start < N: while start < N and s[start] == " ": start += 1 stop = start while stop < N and s[stop] !

by lek tin in "algorithm" access_time 1-min read

Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less 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 left the other as original. Example Input: s = "abcdefg", k = 2 Output: "bacdfeg" Restrictions: The string consists of lower English letters only.

by lek tin in "algorithm" access_time 1-min read

Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters. Example 1 Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Example 2 Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"] Solution class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead.

by lek tin in "algorithm" access_time 1-min read

Shortest Subarray With Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K. If there is no non-empty subarray with sum at least K, return -1. Example 1 Input: A = [1], K = 1 Output: 1 Example 2 Input: A = [1,2], K = 4 Output: -1 Example 3 Input: A = [2,-1,2], K = 3 Output: 3 Note 1 <= A.length <= 50000 -10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9 Solution (sliding window using pointers) This version exceeds time limit Time: O(N)

by lek tin in "algorithm" access_time 2-min read

Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word. Note The order of the output does not matter. Example Input: "word" Output: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"] Example class Solution: def generateAbbreviations(self, word: str) -> List[str]: results = [] self.backtrack(results, word, "", 0, 0) return results def backtrack(self, results, word, curr, start, count): print(curr, start, count) # "" 0 0 # "" 1 1 # "" 2 2 # "" 3 3 # "" 4 4 # ------------ # 3d 4 0 # ------------ # 2r 3 0 # 2r 4 1 # ------------ # 2rd 4 0 # ------------ # 1o 2 0 # 1o 3 1 # 1o 4 2 # ------------ # 1o1d 4 0 # ------------ # 1or 3 0 # 1or 4 1 # ------------ # 1ord 4 0 # ------------ # w 1 0 # w 2 1 # w 3 2 # w 4 3 # ------------ # w2d 4 0 # ------------ # w1r 3 0 # w1r 4 1 # ------------ # w1rd 4 0 # ------------ # wo 2 0 # wo 3 1 # wo 4 2 # ------------ # wo1d 4 0 # ------------ # wor 3 0 # wor 4 1 # ------------ # word 4 0 # ------------ if start == len(word): if count > 0: curr += str(count) # curr could be "4" or "abcd" results.

by lek tin in "algorithm" access_time 2-min read

Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1 Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2 Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Note The input string length won’t exceed 1000.

by lek tin in "algorithm" access_time 1-min read

Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example Input: [4,3,2,7,8,2,3,1] Output: [5,6] Solution class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: N = len(nums) result = [] for num in nums: pos = abs(num) % N if nums[pos] > 0: nums[pos] = -nums[pos] for i in range(1, N+1): if nums[i%N] > 0: result.

by lek tin in "algorithm" access_time 1-min read

First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer. Example 1 Input: [1,2,0] Output: 3 Example 2 Input: [3,4,-1,1] Output: 2 Example 3 Input: [7,8,9,11,12] Output: 1 Solution (hashmap) Time: O(N) Space: O(N) from collections import Counter class Solution: def firstMissingPositive(self, nums: List[int]) -> int: counter = Counter(nums) curr = 1 while True: if curr not in counter: return curr curr += 1 Follow-up Your algorithm should run in O(n) time and uses constant extra space.

by lek tin in "algorithm" access_time 2-min read

Candy

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give? Example 1 Input: [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

by lek tin in "algorithm" access_time 1-min read

Bag of Tokens

You have an initial power P, an initial score of 0 points, and a bag of tokens. Each token can be used at most once, has a value token[i], and has potentially two ways to use it. If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point. If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1 point.

by lek tin in "algorithm" access_time 1-min read