Posts published in “String”

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

By zxi on September 5, 2020

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

class Solution {

public:

int minCost(string s, vector<int>& cost) {

int t = cost[0];

int m = cost[0];

int ans = 0;

for (int i = 1; i < s.length(); ++i) {

if (s[i] != s[i - 1]) {

ans += t - m;

t = m = 0;

}

t += cost[i];

m = max(m, cost[i]);

}

return ans + (t - m);

}

};

python3

class Solution:

def minCost(self, s: str, cost: List[int]) -> int:

s = '*' + s + '*'

cost = [0] + cost + [0]

ans = t = m = 0

for i in range(1, len(s)):

if s[i] != s[i - 1]:

ans += t - m

t = m = 0

t += cost[i]

m = max(m, cost[i])

return ans

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

By zxi on September 5, 2020

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

class Solution {

public:

string modifyString(string s) {

const int n = s.length();

for (int i = 0; i < n; ++i) {

if (s[i] != '?') continue;

for (char c : "abc")

if ((i == 0 || s[i - 1] != c) && (i == n - 1 || s[i + 1] != c)) {

s[i] = c;

break;

}

return s;

}

};

花花酱 LeetCode 1556. Thousand Separator

By zxi on August 22, 2020

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

class Solution {

public:

string thousandSeparator(int n) {

string ans;

int count = 0;

do {

if (count++ % 3 == 0 && ans.size())

ans = "." + ans;

ans = to_string(n % 10) + ans;

n /= 10;

} while (n);

return ans;

}

};

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

By zxi on August 9, 2020

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.

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. ‘)’ -> ‘()’
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
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++

class Solution {

public:

int minInsertions(string s) {

int ans = 0;

int close = 0; // # of ')' needed.

for (char c : s) {

if (c == ')') {

if (--close < 0) {

// need to insert one '('

// ')' -> '()'

++ans;

close += 2;

}

} else {

if (close & 1) {

// need to insert one ')'

// case '(()(' -> '(())('

--close;

++ans;

}

close += 2; // need two ')'s

}

return ans + close;

}

};

花花酱 LeetCode 1507. Reformat Date

By zxi on July 11, 2020

Given a date string in the form Day Month Year, where:

Day is in the set {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"}.
Month is in the set {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}.
Year is in the range [1900, 2100].

Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Example 1:

Input: date = "20th Oct 2052"
Output: "2052-10-20"

Example 2:

Input: date = "6th Jun 1933"
Output: "1933-06-06"

Example 3:

Input: date = "26th May 1960"
Output: "1960-05-26"

Constraints:

The given dates are guaranteed to be valid, so no error handling is necessary.

Solution: String + HashTable

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

C++

// Author: Huahua

class Solution {

public:

string reformatDate(string date) {

stringstream ss(date);

string day, month, year;

ss >> day >> month >> year;

unordered_map<string, string> m{{"Jan", "01"},

{"Feb", "02"},

{"Mar", "03"},

{"Apr", "04"},

{"May", "05"},

{"Jun", "06"},

{"Jul", "07"},

{"Aug", "08"},

{"Sep", "09"},

{"Oct", "10"},

{"Nov", "11"},

{"Dec", "12"}};

day = day.substr(0, day.length() - 2);

if (day.length() == 1) day = "0" + day;

return year + "-" + m[month] + "-" + day;

}

};

Java

// Author: Huahua

class Solution {

public String reformatDate(String date) {

Map<String, String> m = new HashMap<String, String>();

m.put("Jan", "01");

m.put("Feb", "02");

m.put("Mar", "03");

m.put("Apr", "04");

m.put("May", "05");

m.put("Jun", "06");

m.put("Jul", "07");

m.put("Aug", "08");

m.put("Sep", "09");

m.put("Oct", "10");

m.put("Nov", "11");

m.put("Dec", "12");

String[] items = date.split(" ");

String day = items[0].substring(0, items[0].length() - 2);

if (day.length() == 1) day = "0" + day;

return items[2] + "-" + m.get(items[1]) + "-" + day;

}

Python

# Author: Huahua

class Solution:

def reformatDate(self, date: str) -> str:

m = {"Jan": "01", "Feb": "02", "Mar": "03",

"Apr": "04", "May": "05", "Jun": "06",

"Jul": "07", "Aug": "08", "Sep": "09",

"Oct": "10", "Nov": "11", "Dec": "12"}

items = date.split(" ")

day = items[0][:-2]

if len(day) == 1: day = "0" + day

return items[2] + "-" + m[items[1]] + "-" + day