Press "Enter" to skip to content

Posts published in “String”

花花酱 LeetCode 1585. Check If String Is Transformable With Substring Sort Operations

Given two strings s and t, you want to transform string s into string t using the following operation any number of times:

  • Choose a non-empty substring in s and sort it in-place so the characters are in ascending order.

For example, applying the operation on the underlined substring in "14234" results in "12344".

Return true if it is possible to transform string s into string t. Otherwise, return false.

substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "84532", t = "34852"
Output: true
Explanation: You can transform s into t using the following sort operations:
"84532" (from index 2 to 3) -> "84352"
"84352" (from index 0 to 2) -> "34852"

Example 2:

Input: s = "34521", t = "23415"
Output: true
Explanation: You can transform s into t using the following sort operations:
"34521" -> "23451"
"23451" -> "23415"

Example 3:

Input: s = "12345", t = "12435"
Output: false

Example 4:

Input: s = "1", t = "2"
Output: false

Constraints:

  • s.length == t.length
  • 1 <= s.length <= 105
  • s and t only contain digits from '0' to '9'.

Solution: Queue

We can move a smaller digit from right to left by sorting two adjacent digits.
e.g. 18572 -> 18527 -> 18257 -> 12857, but we can not move a larger to the left of a smaller one.

Thus, for each digit in the target string, we find the first occurrence of it in s, and try to move it to the front by checking if there is any smaller one in front of it.

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

C++

Python3

花花酱 LeetCode 1578. Minimum Deletion Cost to Avoid Repeating Letters

Given a string s and an array of integers cost where cost[i] is the cost of deleting the character i in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

Example 1:

Input: s = "abaac", cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter "a" with cost 3 to get "abac" (String without two identical letters next to each other).

Example 2:

Input: s = "abc", cost = [1,2,3]
Output: 0
Explanation: You don't need to delete any character because there are no identical letters next to each other.

Example 3:

Input: s = "aabaa", cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string ("aba").

Constraints:

  • s.length == cost.length
  • 1 <= s.length, cost.length <= 10^5
  • 1 <= cost[i] <= 10^4
  • s contains only lowercase English letters.

Solution: Group by group

For a group of same letters, delete all expect the one with the highest cost.

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

C++

python3

花花酱 LeetCode 1576. Replace All ?’s to Avoid Consecutive Repeating Characters

Given a string s containing only lower case English letters and the ‘?’ character, convert all the ‘?’ characters into lower case letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non ‘?’ characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for ‘?’.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".

Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".

Example 3:

Input: s = "j?qg??b"
Output: "jaqgacb"

Example 4:

Input: s = "??yw?ipkj?"
Output: "acywaipkja"

Constraints:

  • 1 <= s.length <= 100
  • s contains only lower case English letters and ‘?’.

Solution: Greedy

For each ?, find the first one among ‘abc’ that is not same as left or right.

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

C++

花花酱 LeetCode 1556. Thousand Separator

Given an integer n, add a dot (“.”) as the thousands separator and return it in string format.

Example 1:

Input: n = 987
Output: "987"

Example 2:

Input: n = 1234
Output: "1.234"

Example 3:

Input: n = 123456789
Output: "123.456.789"

Example 4:

Input: n = 0
Output: "0"

Constraints:

  • 0 <= n < 2^31

Solution: Digit by digit

Time complexity: O(log^2(n)) -> O(logn)
Space complexity: O(log(n))

C++

花花酱 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++