Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 1544. Make The String Great

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

  • 0 <= i <= s.length - 2
  • s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:

Input: s = "s"
Output: "s"

Constraints:

  • 1 <= s.length <= 100
  • s contains only lower and upper case English letters.

Solution: Stack

Iterator over the string, compare current char with top of the stack, if they are a bad pair, pop the stack (remove both of them). Otherwise, push the current char onto the stack.

input: “abBAcC”
“a”
“ab”
“abB” -> “a”
aA” -> “”
“c”
cC” -> “”
ans = “”

Time complexity: O(n)
Space complexity: O(n)

C++

Java

Python3

花花酱 LeetCode 1542. Find Longest Awesome Substring

Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:

Input: s = "00"
Output: 2

Constraints:

  • 1 <= s.length <= 10^5
  • s consists only of digits.

Solution: Prefix mask + Hashtable

For a palindrome all digits must occurred even times expect one. We can use a 10 bit mask to track the occurrence of each digit for prefix s[0~i]. 0 is even, 1 is odd.

We use a hashtable to track the first index of each prefix state.
If s[0~i] and s[0~j] have the same state which means every digits in s[i+1~j] occurred even times (zero is also even) and it’s an awesome string. Then (j – (i+1) + 1) = j – i is the length of the palindrome. So far so good.

But we still need to consider the case when there is a digit with odd occurrence. We can enumerate all possible ones from 0 to 9, and temporarily flip the bit of the digit and see whether that state happened before.

fisrt_index[0] = -1, first_index[*] = inf
ans = max(ans, j – first_index[mask])

Time complexity: O(n)
Space complexity: O(2^10) = O(1)

C++

Java

Python3

花花酱 LeetCode 1541. Minimum Insertions to Balance a Parentheses String

Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:

  • Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
  • Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.

For example, "())""())(())))" and "(())())))" are balanced, ")()""()))" and "(()))" are not balanced.

You can insert the characters ‘(‘ and ‘)’ at any position of the string to balance it if needed.

Return the minimum number of insertions needed to make s balanced.

Example 1:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.

Example 2:

Input: s = "())"
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.

Example 4:

Input: s = "(((((("
Output: 12
Explanation: Add 12 ')' to balance the string.

Example 5:

Input: s = ")))))))"
Output: 5
Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of '(' and ')' only.

Solution: Counting

Count how many close parentheses we need.

  1. if s[i] is ‘)’, we decrease the counter.
    1. if counter becomes negative, means we need to insert ‘(‘
      1. increase ans by 1, increase the counter by 2, we need one more ‘)’
      2. ‘)’ -> ‘()’
  2. if s[i] is ‘(‘
    1. if we have an odd counter, means there is a unbalanced ‘)’ e.g. ‘(()(‘, counter is 3
      1. need to insert ‘)’, decrease counter, increase ans
      2. ‘(()(‘ -> ‘(())(‘, counter = 2
    2. increase counter by 2, each ‘(‘ needs two ‘)’s. ‘(())(‘ -> counter = 4
  3. Once done, if counter is greater than zero, we need insert that much ‘)s’
    1. counter = 5, ‘((()’ -> ‘((())))))’

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1540. Can Convert String in K Moves

Given two strings s and t, your goal is to convert s into t in kmoves or less.

During the ith (1 <= i <= k) move you can:

  • Choose any index j (1-indexed) from s, such that 1 <= j <= s.length and j has not been chosen in any previous move, and shift the character at that index i times.
  • Do nothing.

Shifting a character means replacing it by the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Shifting a character by i means applying the shift operations i times.

Remember that any index j can be picked at most once.

Return true if it’s possible to convert s into t in no more than k moves, otherwise return false.

Example 1:

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.

Example 2:

Input: s = "abc", t = "bcd", k = 10
Output: false
Explanation: We need to shift each character in s one time to convert it into t. We can shift 'a' to 'b' during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.

Example 3:

Input: s = "aab", t = "bbb", k = 27
Output: true
Explanation: In the 1st move, we shift the first 'a' 1 time to get 'b'. In the 27th move, we shift the second 'a' 27 times to get 'b'.

Constraints:

  • 1 <= s.length, t.length <= 10^5
  • 0 <= k <= 10^9
  • st contain only lowercase English letters.

Solution: HashTable

Count how many times a d-shift has occurred.
a -> c is a 2-shift, z -> b is also 2-shift
a -> d is a 3-shift
a -> a is a 0-shift that we can skip
if a d-shift happened for the first time, we need at least d moves
However, if it happened for c times, we need at least d + 26 * c moves
e.g. we can do a 2-shift at the 2nd move, do another one at 2 + 26 = 28th move and do another at 2 + 26*2 = 54th move, and so on.
Need to find maximum move we need and make sure that one is <= k.
Since we can pick any index to shift, so the order doesn’t matter. We can start from left to right.

Time complexity: O(n)
Space complexity: O(26) = O(1)

C++

花花酱 LeetCode 1539. Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 1000
  • 1 <= k <= 1000
  • arr[i] < arr[j] for 1 <= i < j <= arr.length

Solution 1: HashTable

Store all the elements into a hashtable, and check from 1 to max(arr).

Time complexity: O(max(arr)) ~ O(1000)
Space complexity: O(n)

C++

Solution 2: Binary Search

We can find the smallest index l using binary search, s.t.
arr[l] – l + 1 >= k
which means we missed at least k numbers at index l.
And the answer will be l + k.

Time complexity: O(logn)
Space complexity: O(1)

C++

Java

Python3