Given a string, determine if a permutation of the string could form a palindrome. Example 1 Input: "code" Output: false Example 2 Input: "aab" Output: true Example 3 Input: "carerac" Output: true Solution class Solution: def canPermutePalindrome(self, s: str) -> bool: lookup = set() for c in s: if c not in lookup: lookup.add(c) else: lookup.remove(c) return len(lookup) <= 1
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1. Example 1 s = "leetcode" return 0. Example 2 s = "loveleetcode", return 2. Solution Java class Solution { public int firstUniqChar(String s) { int[] counter = new int[256]; for ( char c: s.toCharArray() ) { counter[c] += 1; } for ( int i = 0; i < s.length(); i++) { if (counter[s.
Implement a MaxQueue class that has the following methods: public interface MaxQueue { public void add(Long l); public Long poll(); public Long pollMax(); } All 3 operations should take on average O(logN) time. Solution // "static void main" must be defined in a public class. public class Main { public static void main(String[] args) throws Exception { System.out.println("Hello World!"); DoubleLinkedList list = new DoubleLinkedList(); MaxQueue maxQ = new MaxQueue(); maxQ.add(5); maxQ.
Given an array of characters, compress it in-place. The length after compression must always be smaller than or equal to the original array. Every element of the array should be a character (not int) of length 1. After you are done modifying the input array in-place, return the new length of the array. Follow up Could you solve it using only O(1) extra space? Example 1 Input: ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: "aa" is replaced by "a2".
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation. Example 1 Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Example 2 Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Example 3 Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 Solution class Solution: def evalRPN(self, tokens: List[str]) -> int: if not tokens: return None stack = [] operators = set(["+", "-", "*", "/"]) N = len(tokens) curr = 0 while curr < N: while curr < N and tokens[curr] not in operators: stack.
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] !
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.
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.
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)
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.