Huahua’s Tech Road

花花酱 LeetCode 1974. Minimum Time to Type Word Using Special Typewriter

By zxi on December 31, 2021

There is a special typewriter with lowercase English letters 'a' to 'z' arranged in a circle with a pointer. A character can only be typed if the pointer is pointing to that character. The pointer is initially pointing to the character 'a'.

Each second, you may perform one of the following operations:

Move the pointer one character counterclockwise or clockwise.
Type the character the pointer is currently on.

Given a string word, return the minimum number of seconds to type out the characters in word.

Example 1:

Input: word = "abc"
Output: 5
Explanation: 
The characters are printed as follows:
- Type the character 'a' in 1 second since the pointer is initially on 'a'.
- Move the pointer clockwise to 'b' in 1 second.
- Type the character 'b' in 1 second.
- Move the pointer clockwise to 'c' in 1 second.
- Type the character 'c' in 1 second.

Example 2:

Input: word = "bza"
Output: 7
Explanation:
The characters are printed as follows:
- Move the pointer clockwise to 'b' in 1 second.
- Type the character 'b' in 1 second.
- Move the pointer counterclockwise to 'z' in 2 seconds.
- Type the character 'z' in 1 second.
- Move the pointer clockwise to 'a' in 1 second.
- Type the character 'a' in 1 second.

Example 3:

Input: word = "zjpc"
Output: 34
Explanation:
The characters are printed as follows:
- Move the pointer counterclockwise to 'z' in 1 second.
- Type the character 'z' in 1 second.
- Move the pointer clockwise to 'j' in 10 seconds.
- Type the character 'j' in 1 second.
- Move the pointer clockwise to 'p' in 6 seconds.
- Type the character 'p' in 1 second.
- Move the pointer counterclockwise to 'c' in 13 seconds.
- Type the character 'c' in 1 second.

Constraints:

1 <= word.length <= 100
word consists of lowercase English letters.

Solution: Clockwise or Counter-clockwise?

For each pair of (prev, curr), choose the shortest distance.
One is abs(p – c), another is 26 – abs(p – c).
Don’t forget to add 1 for typing itself.

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

C++

// Author: Huahua

class Solution {

public:

int minTimeToType(string word) {

int ans = 0;

char p = 'a';

for (char c : word) {

ans += 1 + min(abs(c - p), 26 - abs(c - p));

p = c;

}

return ans;

}

};

花花酱 LeetCode 1967. Number of Strings That Appear as Substrings in Word

By zxi on December 31, 2021

Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in word.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "a" appears as a substring in "abc".
- "abc" appears as a substring in "abc".
- "bc" appears as a substring in "abc".
- "d" does not appear as a substring in "abc".
3 of the strings in patterns appear as a substring in word.

Example 2:

Input: patterns = ["a","b","c"], word = "aaaaabbbbb"
Output: 2
Explanation:
- "a" appears as a substring in "aaaaabbbbb".
- "b" appears as a substring in "aaaaabbbbb".
- "c" does not appear as a substring in "aaaaabbbbb".
2 of the strings in patterns appear as a substring in word.

Example 3:

Input: patterns = ["a","a","a"], word = "ab"
Output: 3
Explanation: Each of the patterns appears as a substring in word "ab".

Constraints:

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] and word consist of lowercase English letters.

Solution: Brute Force

We can use count_if for 1-liner.

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

C++

// Author: Huahua

class Solution {

public:

int numOfStrings(vector<string>& patterns, string word) {

return count_if(begin(patterns), end(patterns), [&](string& p) {

return word.find(p) != string::npos;

});

}

};

花花酱 LeetCode 1962. Remove Stones to Minimize the Total

By zxi on December 31, 2021

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the i^th pile, and an integer k. You should apply the following operation exactly k times:

Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).

Example 1:

Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.

Example 2:

Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [4,3,3,7].
- Apply the operation on pile 3. The resulting piles are [4,3,3,4].
- Apply the operation on pile 0. The resulting piles are [2,3,3,4].
The total number of stones in [2,3,3,4] is 12.

Constraints:

1 <= piles.length <= 10⁵
1 <= piles[i] <= 10⁴
1 <= k <= 10⁵

Solution: Greedy / Heap

Always choose the largest pile to remove.

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

C++

// Author: Huahua

class Solution {

public:

int minStoneSum(vector<int>& piles, int k) {

int total = accumulate(begin(piles), end(piles), 0);

priority_queue<int> q(begin(piles), end(piles));

while (k--) {

int curr = q.top(); q.pop();

int remove = curr / 2;

total -= remove;

q.push(curr - remove);

}

return total;

}

};

花花酱 LeetCode 1961. Check If String Is a Prefix of Array

By zxi on December 31, 2021

Given a string s and an array of strings words, determine whether s is a prefix string of words.

A string s is a prefix string of words if s can be made by concatenating the first k strings in words for some positive k no larger than words.length.

Return true if s is a prefix string of words, or false otherwise.

Example 1:

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"]
Output: true
Explanation:
s can be made by concatenating "i", "love", and "leetcode" together.

Example 2:

Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"]
Output: false
Explanation:
It is impossible to make s using a prefix of arr.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 20
1 <= s.length <= 1000
words[i] and s consist of only lowercase English letters.

Solution: Concat and test

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

C++

// Author: Huahua

class Solution {

public:

bool isPrefixString(string s, vector<string>& words) {

string t;

for (const string& w : words) {

t += w;

if (t.length() >= s.length()) break;

}

return t == s;

}

};

花花酱 LeetCode 1957. Delete Characters to Make Fancy String

By zxi on December 31, 2021

A fancy string is a string where no three consecutive characters are equal.

Given a string s, delete the minimum possible number of characters from s to make it fancy.

Return the final string after the deletion. It can be shown that the answer will always be unique.

Example 1:

Input: s = "leeetcode"
Output: "leetcode"
Explanation:
Remove an 'e' from the first group of 'e's to create "leetcode".
No three consecutive characters are equal, so return "leetcode".

Example 2:

Input: s = "aaabaaaa"
Output: "aabaa"
Explanation:
Remove an 'a' from the first group of 'a's to create "aabaaaa".
Remove two 'a's from the second group of 'a's to create "aabaa".
No three consecutive characters are equal, so return "aabaa".

Example 3:

Input: s = "aab"
Output: "aab"
Explanation: No three consecutive characters are equal, so return "aab".

Constraints:

1 <= s.length <= 10⁵
s consists only of lowercase English letters.

Solution:

Skip the current letter if there are already two same letters in the output string.

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

C++

// Author: Huahua

class Solution {

public:

string makeFancyString(string s) {

string ans;

int count = 0;

for (char c : s) {

if (ans.empty() || c != ans.back())

count = 1;

else if (++count >= 3) continue;

ans += c;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1974. Minimum Time to Type Word Using Special Typewriter

Solution: Clockwise or Counter-clockwise?

C++

花花酱 LeetCode 1967. Number of Strings That Appear as Substrings in Word

Solution: Brute Force

C++

花花酱 LeetCode 1962. Remove Stones to Minimize the Total

Solution: Greedy / Heap

C++

花花酱 LeetCode 1961. Check If String Is a Prefix of Array

Solution: Concat and test

C++

花花酱 LeetCode 1957. Delete Characters to Make Fancy String

Solution:

C++