Posts tagged as “string”

花花酱 LeetCode 1684. Count the Number of Consistent Strings

By zxi on December 12, 2020

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Example 2:

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Explanation: All strings are consistent.

Example 3:

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Explanation: Strings "cc", "acd", "ac", and "d" are consistent.

Constraints:

1 <= words.length <= 10⁴
1 <= allowed.length <=26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Solution: Hashtable

Time complexity: O(sum(len(word))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countConsistentStrings(string allowed, vector<string>& words) {

vector<int> m(26);

for (char c : allowed) m[c - 'a'] = 1;

int ans = 0;

for (const string& w : words)

ans += all_of(begin(w), end(w), [&m](char c) { return m[c - 'a']; });

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:

return sum(all(c in allowed for c in w) for w in words)

花花酱 LeetCode 1678. Goal Parser Interpretation

By zxi on December 5, 2020

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G", "()" and/or "(al)" in some order. The Goal Parser will interpret "G" as the string "G", "()" as the string "o", and "(al)" as the string "al". The interpreted strings are then concatenated in the original order.

Given the string command, return the Goal Parser‘s interpretation of command.

Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al
The final concatenated result is "Goal".

Example 2:

Input: command = "G()()()()(al)"
Output: "Gooooal"

Example 3:

Input: command = "(al)G(al)()()G"
Output: "alGalooG"

Constraints:

1 <= command.length <= 100
command consists of "G", "()", and/or "(al)" in some order.

Solution: String

If we encounter ‘(‘ check the next character to determine whether it’s ‘()’ or ‘(al’)

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

C++

class Solution {

public:

string interpret(string command) {

string ans;

for (int i = 0; i < command.size(); ++i) {

if (command[i] == 'G') ans += "G";

else if (command[i] == '(') {

if (command[i + 1] == ')') ans += "o";

else ans += "al";

}

return ans;

}

};

Python3

class Solution:

def interpret(self, command: str) -> str:

ans = []

for i, c in enumerate(command):

if c == 'G': ans.append('G')

elif c == '(':

ans.append('o' if command[i + 1] == ')' else 'al')

return ''.join(ans)

花花酱 LeetCode 1286. Iterator for Combination

By zxi on November 30, 2020

Design an Iterator class, which has:

A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
A function next() that returns the next combination of length combinationLength in lexicographical order.
A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

1 <= combinationLength <= characters.length <= 15
There will be at most 10^4 function calls per test.
It’s guaranteed that all calls of the function next are valid.

Solution: Bitmask

Use a bitmask to represent the chars selected.
start with (2^n – 1), decrease the mask until there are c bit set.
stop when mask reach to 0.

mask: 111 => abc
mask: 110 => ab
mask: 101 => ac
mask: 011 => bc
mask: 000 => “” Done

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

C++

class CombinationIterator {

public:

CombinationIterator(string characters, int combinationLength):

chars_(rbegin(characters), rend(characters)),

length_(combinationLength),

mask_((1 << characters.size()) - 1) {}

string next() {

hasNext();

string ans;

for (int i = chars_.size() - 1; i >= 0 ; --i)

if ((mask_ >> i) & 1)

ans.push_back(chars_[i]);

--mask_;

return ans;

}

bool hasNext() {

while (mask_ >= 0 && __builtin_popcount(mask_) != length_) --mask_;

return mask_ > 0;

}

private:

int mask_ = 0;

const int length_;

const string chars_;

};

花花酱 LeetCode 1668. Maximum Repeating Substring

By zxi on November 28, 2020

For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word‘s maximum k-repeating value is the highest value k where word is k-repeating in sequence. If word is not a substring of sequence, word‘s maximum k-repeating value is 0.

Given strings sequence and word, return the maximum k-repeating value of word in sequence.

Example 1:

Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab" is a substring in "ababc".

Example 2:

Input: sequence = "ababc", word = "ba"
Output: 1
Explanation: "ba" is a substring in "ababc". "baba" is not a substring in "ababc".

Example 3:

Input: sequence = "ababc", word = "ac"
Output: 0
Explanation: "ac" is not a substring in "ababc".

Constraints:

1 <= sequence.length <= 100
1 <= word.length <= 100
sequence and word contains only lowercase English letters.

Solution: Brute Force

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

C++

class Solution {

public:

int maxRepeating(string sequence, string word) {

string s(word);

for (int i = 1;;++i) {

if (sequence.find(s) == string::npos) return i - 1;

s += word;

}

return -1;

}

};

花花酱 LeetCode 1663. Smallest String With A Given Numeric Value

By zxi on November 22, 2020

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters’ numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example 1:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

Example 2:

Input: n = 5, k = 73
Output: "aaszz"

Constraints:

1 <= n <= 10⁵
n <= k <= 26 * n

Solution: Greedy, Fill in reverse order

Fill the entire string with ‘a’, k-=n, then fill in reverse order, replace ‘a’ with ‘z’ until not enough k left.

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

C++

// Author: Huahua

class Solution {

public:

string getSmallestString(int n, int k) {

string ans(n, 'a');

k -= n;

while (k) {

int d = min(k, 25);

ans[--n] += d;

k -= d;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def getSmallestString(self, n: int, k: int) -> str:

ans = ['a'] * n

k -= n

i = n - 1

while k:

d = min(k, 25)

ans[i] = chr(ord(ans[i]) + d)

k -= d

i -= 1

return ''.join(ans)