A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros. For example, a string such as “substitution” could be abbreviated as (but not limited to): “s10n” (“s ubstitutio n”) “sub4u4” (“sub stit u tion”) “12” (“substitution”) “su3i1u2on” (“su bst i t u ti on”) “substitution” (no substrings replaced) The following are not valid abbreviations: ...
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”. The testcases will be generated such that the answer is unique. A substring is a contiguous sequence of characters within the string. Example 1: Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. Example 2: Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window. Example 3: Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string. Constraints: ...
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3]. ...
1482. Minimum Number of Days to Make m Bouquets Given a string s, reverse only all the vowels in the string and return it. The vowels are ‘a’, ’e’, ‘i’, ‘o’, and ‘u’, and they can appear in both cases. Example 1: Input: s = "hello" Output: "holle" Example 2: Input: s = "leetcode" Output: "leotcede" Constraints: 1 <= s.length <= 3 * 105 s consist of printable ASCII characters. Solution class Solution { public String reverseVowels(String s) { Set<Character> vowels = new HashSet<>(); vowels.addAll(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')); int lo = 0; int hi = s.length() - 1; char[] word = s.toCharArray(); while (lo < hi) { while (lo < hi && !vowels.contains(word[lo])) { lo++; } while (lo < hi && !vowels.contains(word[hi])) { hi--; } char c = word[lo]; word[lo] = word[hi]; word[hi] = c; lo++; hi--; } return new String(word); } }
475. Heaters Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses. Every house can be warmed, as long as the house is within the heater’s warm radius range. Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses. ...
11. Container With Most Water Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water. Notice that you may not slant the container. ...
680. Valid Palindrome II Given a string s, return true if the s can be palindrome after deleting at most one character from it. Example 1: Input: s = "aba" Output: true Example 2: Input: s = "abca" Output: true Explanation: You could delete the character 'c'. Example 3: Input: s = "abc" Output: false Constraints: 1 <= s.length <= 105 s consists of lowercase English letters. Solution class Solution { public boolean validPalindrome(String s) { return palindrom(s, 0); } boolean palindrom(String s, int count) { int i = 0; int n = s.length(); while (i < n / 2) { char c1 = s.charAt(i); char c2 = s.charAt(n - i - 1); if (c1 == c2) { i++; continue; } else { if (count == 0) { StringBuilder sb1 = new StringBuilder(s); sb1.deleteCharAt(i); boolean res1 = palindrom(sb1.toString(), 1); if (res1) return true; StringBuilder sb2 = new StringBuilder(s); sb2.deleteCharAt(n - i - 1); return palindrom(sb2.toString(), 1); } return false; } } return true; } } Solution 2021-11-21 class Solution { public boolean validPalindrome(String s) { return validatePalindrom(s, 1, 0, s.length() - 1); } boolean validatePalindrom(String s, int deleted, int lo, int hi) { while (lo < hi) { if (s.charAt(lo) == s.charAt(hi)) { lo++; hi--; } else { if (deleted == 0) { return false; } return validatePalindrom(s, 0, lo + 1, hi) || validatePalindrom(s, 0, lo, hi - 1); } } return true; } } Solution 2022-01-22 class Solution { public boolean validPalindrome(String s) { char[] symbols = s.toCharArray(); return validPalindrome(symbols, 0, s.length() - 1, 1); } boolean validPalindrome(char[] symbols, int i, int j, int count) { while (i < j) { if (symbols[i] == symbols[j]) { i++; j--; continue; } else { if (count > 0) { return validPalindrome(symbols, i, j - 1, 0) || validPalindrome(symbols, i + 1, j, 0); } else { return false; } } } return true; } }
67. Add Binary Given two binary strings a and b, return their sum as a binary string. Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: "10101" Constraints: 1 <= a.length, b.length <= 104 a and b consist only of ‘0’ or ‘1’ characters. Each string does not contain leading zeros except for the zero itself. Solution class Solution { public String addBinary(String a, String b) { int i = a.length() - 1; int j = b.length() - 1; int carry = 0; StringBuilder sb = new StringBuilder(); while (i >= 0 || j >= 0) { int c1 = (i >= 0) ? a.charAt(i) - '0': 0; int c2 = (j >= 0) ? b.charAt(j) - '0': 0; int c3 = c1 + c2 + carry; if (carry > 0) { carry = 0; } if (c3 == 3) { carry = 1; sb.insert(0, '1'); } else if (c3 == 2) { carry = 1; sb.insert(0, '0'); } else if (c3 == 1) { sb.insert(0, '1'); } else { sb.insert(0, '0'); } i--; j--; } if (carry > 0) { sb.insert(0, '1'); } return sb.toString(); } public String addBinary2(String a, String b) { Integer i1 = Integer.parseInt(a, 2); Integer i2 = Integer.parseInt(b, 2); return Integer.toBinaryString(i1 + i2); } }
A string s of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts. Example 1: Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts. Note: ...