Posts tagged as “string”

花花酱 LeetCode 1897. Redistribute Characters to Make All Strings Equal

By zxi on August 11, 2021

You are given an array of strings words (0-indexed).

In one operation, pick two distinct indices i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j].

Return true if you can make every string in words equal using any number of operations, and false otherwise.

Example 1:

Input: words = ["abc","aabc","bc"]
Output: true
Explanation: Move the first 'a' in words[1] to the front of words[2],
to make words[1] = "abc" and words[2] = "abc".
All the strings are now equal to "abc", so return true.

Example 2:

Input: words = ["ab","a"]
Output: false
Explanation: It is impossible to make all the strings equal using the operation.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Solution: Hashtable

Count the frequency of each character, it must be a multiplier of n such that we can evenly distribute it to all the words.
e.g. n = 3, a = 9, b = 6, c = 3, each word will be “aaabbc”.

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

C++

// Author: Huahua

class Solution {

public:

bool makeEqual(vector<string>& words) {

vector<int> freq(26);

for (const auto& word : words)

for (char c : word)

++freq[c - 'a'];

for (int f : freq)

if (f % words.size()) return false;

return true;

}

};

Python3 one-liner

# Author: Huahua

class Solution:

def makeEqual(self, words: List[str]) -> bool:

return all(c % len(words) == 0 for c in Counter(''.join(words)).values())

花花酱 LeetCode 1888. Minimum Number of Flips to Make the Binary String Alternating

By zxi on August 9, 2021

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

Type-1: Remove the character at the start of the string s and append it to the end of the string.
Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Example 1:

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating.

Example 3:

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".

Constraints:

1 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Solution: Sliding Window

Trying all possible rotations will take O(n²) that leads to TLE, we have to do better.

concatenate the s to itself, then using a sliding window length of n to check how many count needed to make the string in the window alternating which will cover all possible rotations. We can update the count in O(1) when moving to the next window.

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

C++

// Author: Huahua
class Solution {
public:
  int minFlips(string s) {
    const int n = s.length();    
    int ans = INT_MAX;
    for (int i = 0, c0 = 0, c1 = 1, a0 = 0, a1 = 0; i < 2 * n; ++i, c0 ^= 1, c1 ^= 1) {
      if (s[i % n] - '0' != c0) ++a0;
      if (s[i % n] - '0' != c1) ++a1;
      if (i < n - 1) continue;
      if (i >= n) {
        if (s[i - n] - '0' != c0 ^ (n & 1)) --a0;
        if (s[i - n] - '0' != c1 ^ (n & 1)) --a1;
      }
      ans = min({ans, a0, a1});      
    }    
    return ans;
  }
};

花花酱 LeetCode 1881. Maximum Value after Insertion

By zxi on August 8, 2021

You are given a very large integer n, represented as a string, and an integer digit x. The digits in n and the digit x are in the inclusive range [1, 9], and n may represent a negative number.

You want to maximize n‘s numerical value by inserting x anywhere in the decimal representation of n. You cannot insert x to the left of the negative sign.

For example, if n = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.
If n = -55 and x = 2, it would be best to insert it before the first 5, making n = -255.

Return a string representing the maximum value of n after the insertion.

Example 1:

Input: n = "99", x = 9
Output: "999"
Explanation: The result is the same regardless of where you insert 9.

Example 2:

Input: n = "-13", x = 2
Output: "-123"
Explanation: You can make n one of {-213, -123, -132}, and the largest of those three is -123.

Constraints:

1 <= n.length <= 10⁵
1 <= x <= 9
The digits in n are in the range [1, 9].
n is a valid representation of an integer.
In the case of a negative n, it will begin with '-'.

Solution: Greedy

Find the best position to insert x. For positive numbers, insert x to the first position i such that s[i] < x or s[i] > x for negatives.

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

C++

// Author: Huahua

class Solution {

public:

string maxValue(string n, int x) {

const int l = n.length();

if (n[0] == '-') {

for (int i = 1; i <= l; ++i)

if (i == l || n[i] - '0' > x)

return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i);

} else {

for (int i = 0; i <= l; ++i)

if (i == l || x > n[i] - '0')

return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i);

}

return "";

}

};

花花酱 LeetCode 1880. Check if Word Equals Summation of Two Words

By zxi on August 8, 2021

The letter value of a letter is its position in the alphabet starting from 0 (i.e. 'a' -> 0, 'b' -> 1, 'c' -> 2, etc.).

The numerical value of some string of lowercase English letters s is the concatenation of the letter values of each letter in s, which is then converted into an integer.

For example, if s = "acb", we concatenate each letter’s letter value, resulting in "021". After converting it, we get 21.

You are given three strings firstWord, secondWord, and targetWord, each consisting of lowercase English letters 'a' through 'j' inclusive.

Return true if the summation of the numerical values of firstWord and secondWord equals the numerical value of targetWord, or false otherwise.

Example 1:

Input: firstWord = "acb", secondWord = "cba", targetWord = "cdb"
Output: true
Explanation:
The numerical value of firstWord is "acb" -> "021" -> 21.
The numerical value of secondWord is "cba" -> "210" -> 210.
The numerical value of targetWord is "cdb" -> "231" -> 231.
We return true because 21 + 210 == 231.

Example 2:

Input: firstWord = "aaa", secondWord = "a", targetWord = "aab"
Output: false
Explanation: 
The numerical value of firstWord is "aaa" -> "000" -> 0.
The numerical value of secondWord is "a" -> "0" -> 0.
The numerical value of targetWord is "aab" -> "001" -> 1.
We return false because 0 + 0 != 1.

Example 3:

Input: firstWord = "aaa", secondWord = "a", targetWord = "aaaa"
Output: true
Explanation: 
The numerical value of firstWord is "aaa" -> "000" -> 0.
The numerical value of secondWord is "a" -> "0" -> 0.
The numerical value of targetWord is "aaaa" -> "0000" -> 0.
We return true because 0 + 0 == 0.

Constraints:

1 <= firstWord.length, secondWord.length, targetWord.length <= 8
firstWord, secondWord, and targetWord consist of lowercase English letters from 'a' to 'j' inclusive.

Solution: Brute Force

Tips: Write a reusable function to compute the score of a word.

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

C++

// Author: Huahua

class Solution {

public:

bool isSumEqual(string firstWord, string secondWord, string targetWord) {

auto score = [](string_view s) {

int ans = 0;

for (char c : s)

ans = ans * 10 + (c - 'a');

return ans;

};

return score(firstWord) + score(secondWord) == score(targetWord);

}

};

花花酱 LeetCode 1876. Substrings of Size Three with Distinct Characters

By zxi on August 6, 2021

A string is good if there are no repeated characters.

Given a string s, return the number of good substrings of length three in s.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

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

Example 1:

Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz". 
The only good substring of length 3 is "xyz".

Example 2:

Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".

Constraints:

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

Solution: Brute Force w/ (Hash)Set

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

C++

class Solution {

public:

int countGoodSubstrings(string s) {

int ans = 0;

for (int i = 0; i + 2 < s.length(); ++i)

ans += set<char>(s.begin() + i, s.begin() + i + 3).size() == 3;

return ans;

}

};

Python3

class Solution:

def countGoodSubstrings(self, s: str) -> int:

return sum(len(set(s[i:i + 3])) == 3 for i in range(len(s) - 2))