Posts tagged as “string”

花花酱 LeetCode 1736. Latest Time by Replacing Hidden Digits

By zxi on January 23, 2021

You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).

The valid times are those inclusively between 00:00 and 23:59.

Return the latest valid time you can get from time by replacing the hidden digits.

Example 1:

Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.

Example 2:

Input: time = "0?:3?"
Output: "09:39"

Example 3:

Input: time = "1?:22"
Output: "19:22"

Constraints:

time is in the format hh:mm.
It is guaranteed that you can produce a valid time from the given string.

Solution 1: Brute Force

Enumerate all possible clock in reverse order and find the first matching one.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

for (int m = 60 * 24 - 1; m >= 0; --m) {

int hh = m / 60;

int mm = m % 60;

if (time[0] != '?' && time[0] - '0' != hh / 10) continue;

if (time[1] != '?' && time[1] - '0' != hh % 10) continue;

if (time[3] != '?' && time[3] - '0' != mm / 10) continue;

if (time[4] != '?' && time[4] - '0' != mm % 10) continue;

time[0] = (hh / 10) + '0';

time[1] = (hh % 10) + '0';

time[3] = (mm / 10) + '0';

time[4] = (mm % 10) + '0';

break;

}

return time;

}

};

Solution 2: Rules

Using rules, fill from left to right.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

if (time[0] == '?') time[0] = time[1] >= '4' && time[1] <= '9' ? '1' : '2';

if (time[1] == '?') time[1] = time[0] == '2' ? '3' : '9';

if (time[3] == '?') time[3] = '5';

if (time[4] == '?') time[4] = '9';

return time;

}

};

花花酱 LeetCode 1717. Maximum Score From Removing Substrings

By zxi on January 9, 2021

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

Remove substring "ab" and gain x points.
- For example, when removing "ab" from "cabxbae" it becomes "cxbae".
Remove substring "ba" and gain y points.
- For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

Constraints:

1 <= s.length <= 10⁵
1 <= x, y <= 10⁴
s consists of lowercase English letters.

Solution: Greedy + Stack

Remove the pattern with the larger score first.

Using a stack to remove all occurrences of a pattern in place in O(n) Time.

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

C++

// Author: Huahua

class Solution {

public:

int maximumGain(string s, int x, int y) {

// Remove patttern p from s for t points each.

// Returns the total score.

auto remove = [&](const string& p, int t) {

int total = 0;

int i = 0;

for (int j = 0; j < s.size(); ++j, ++i) {

s[i] = s[j];

if (i && s[i - 1] == p[0] && s[i] == p[1]) {

i -= 2;

total += t;

}

s.resize(i);

return total;

};

string px{"ab"};

string py{"ba"};

if (y > x) {

swap(px, py);

swap(x, y);

}

return remove(px, x) + remove(py, y);

}

};

花花酱 LeetCode 1704. Determine if String Halves Are Alike

By zxi on December 27, 2020

You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.

Two strings are alike if they have the same number of vowels ('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'). Notice that s contains uppercase and lowercase letters.

Return true if a and b are alike. Otherwise, return false.

Example 1:

Input: s = "book"
Output: true
Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Example 2:

Input: s = "textbook"
Output: false
Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.

Example 3:

Input: s = "MerryChristmas"
Output: false

Example 4:

Input: s = "AbCdEfGh"
Output: true

Constraints:

2 <= s.length <= 1000
s.length is even.
s consists of uppercase and lowercase letters.

Solution: Counting

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

Python3

# Author: Huahua

class Solution:

def halvesAreAlike(self, s: str) -> bool:

def count(s: str) -> int:

return sum(c in 'aeiouAEIOU' for c in s)

n = len(s)

return count(s[:n//2]) == count(s[n//2:])

花花酱 LeetCode 1702. Maximum Binary String After Change

By zxi on December 26, 2020

You are given a binary string binary consisting of only 0‘s or 1‘s. You can apply each of the following operations any number of times:

Operation 1: If the number contains the substring "00", you can replace it with "10".
- For example, "00010" -> "10010“
Operation 2: If the number contains the substring "10", you can replace it with "01".
- For example, "00010" -> "00001"

Return the maximum binary string you can obtain after any number of operations. Binary string x is greater than binary string y if x‘s decimal representation is greater than y‘s decimal representation.

Example 1:

Input: binary = "000110"
Output: "111011"
Explanation: A valid transformation sequence can be:
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

Example 2:

Input: binary = "01"
Output: "01"
Explanation: "01" cannot be transformed any further.

Constraints:

1 <= binary.length <= 10⁵
binary consist of '0' and '1'.

Solution: Greedy + Counting

Leading 1s are good, no need to change them.
For the rest of the string
1. Apply operation 2 to make the string into 3 parts, leading 1s, middle 0s and tailing 1s.
e.g. 11010101 => 11001101 => 11001011 => 11000111
2. Apply operation 1 to make flip zeros to ones except the last one.
e.g. 11000111 => 11100111 => 11110111

There will be only one zero (if the input string is not all 1s) is the final largest string, the position of the zero is leading 1s + zeros – 1.

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

C++

class Solution {

public:

string maximumBinaryString(string s) {

const int n = s.length();

int l = 0;

int z = 0;

for (char& c : s) {

if (c == '0') {

++z;

} else if (z == 0) { // leading 1s

++l;

}

c = '1';

}

if (l != n) s[l + z - 1] = '0';

return s;

}

};

花花酱 LeetCode 1694. Reformat Phone Number

By zxi on December 20, 2020

You are given a phone number as a string number. number consists of digits, spaces ' ', and/or dashes '-'.

You would like to reformat the phone number in a certain manner. Firstly, remove all spaces and dashes. Then, group the digits from left to right into blocks of length 3 until there are 4 or fewer digits. The final digits are then grouped as follows:

2 digits: A single block of length 2.
3 digits: A single block of length 3.
4 digits: Two blocks of length 2 each.

The blocks are then joined by dashes. Notice that the reformatting process should never produce any blocks of length 1 and produce at most two blocks of length 2.

Return the phone number after formatting.

Example 1:

Input: number = "1-23-45 6"
Output: "123-456"
Explanation: The digits are "123456".
Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123".
Step 2: There are 3 digits remaining, so put them in a single block of length 3. The 2nd block is "456".
Joining the blocks gives "123-456".

Example 2:

Input: number = "123 4-567"
Output: "123-45-67"
Explanation: The digits are "1234567".
Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123".
Step 2: There are 4 digits left, so split them into two blocks of length 2. The blocks are "45" and "67".
Joining the blocks gives "123-45-67".

Example 3:

Input: number = "123 4-5678"
Output: "123-456-78"
Explanation: The digits are "12345678".
Step 1: The 1st block is "123".
Step 2: The 2nd block is "456".
Step 3: There are 2 digits left, so put them in a single block of length 2. The 3rd block is "78".
Joining the blocks gives "123-456-78".

Example 4:

Input: number = "12"
Output: "12"

Example 5:

Input: number = "--17-5 229 35-39475 "
Output: "175-229-353-94-75"

Constraints:

2 <= number.length <= 100
number consists of digits and the characters '-' and ' '.
There are at least two digits in number.

Solution:

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

C++

// Author: Huahua

class Solution {

public:

string reformatNumber(string number) {

string ans;

const int total = count_if(begin(number), end(number),

[](char c) { return isdigit(c); });

int l = 0;

for (char c : number) {

if (!isdigit(c)) continue;

ans += c;

++l;

if ((l % 3 == 0 && total - l >= 4) ||

(total % 3 != 0 && total - l == 2)

|| (total % 3 == 0 && total - l == 3))

ans += "-";

}

return ans;

}

};