Posts published in “String”

花花酱 LeetCode 1839. Longest Substring Of All Vowels in Order

By zxi on April 25, 2021

A string is considered beautiful if it satisfies the following conditions:

Each of the 5 English vowels ('a', 'e', 'i', 'o', 'u') must appear at least once in it.
The letters must be sorted in alphabetical order (i.e. all 'a's before 'e's, all 'e's before 'i's, etc.).

For example, strings "aeiou" and "aaaaaaeiiiioou" are considered beautiful, but "uaeio", "aeoiu", and "aaaeeeooo" are not beautiful.

Given a string word consisting of English vowels, return the length of the longest beautiful substring of word. If no such substring exists, return 0.

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

Example 1:

Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
Output: 13
Explanation: The longest beautiful substring in word is "aaaaeiiiiouuu" of length 13.

Example 2:

Input: word = "aeeeiiiioooauuuaeiou"
Output: 5
Explanation: The longest beautiful substring in word is "aeiou" of length 5.

Example 3:

Input: word = "a"
Output: 0
Explanation: There is no beautiful substring, so return 0.

Constraints:

1 <= word.length <= 5 * 10⁵
word consists of characters 'a', 'e', 'i', 'o', and 'u'.

Solution: Counter

Use a counter to track how many unique vowels we saw so far. Reset the counter whenever the s[i] < s[i-1]. Incase the counter if s[i] > s[i – 1]. When counter becomes 5, we know we found a valid substring.

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

C++

// Author: Huahua

class Solution {

public:

int longestBeautifulSubstring(string word) {

const int n = word.length();

int ans = 0;

char p = 'a' - 1;

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

if (word[i] < p) {

vowels = (word[i] == 'a');

l = i;

} else if (word[i] > p) {

++vowels;

}

if (vowels == 5)

ans = max(ans, i - l + 1);

p = word[i];

}

return ans;

}

};

花花酱 LeetCode 1816. Truncate Sentence

By zxi on April 6, 2021

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each of the words consists of only uppercase and lowercase English letters (no punctuation).

For example, "Hello World", "HELLO", and "hello world hello world" are all sentences.

You are given a sentence s and an integer k. You want to truncate s such that it contains only the first k words. Return s after truncating it.

Example 1:

Input: s = "Hello how are you Contestant", k = 4
Output: "Hello how are you"
Explanation:
The words in s are ["Hello", "how" "are", "you", "Contestant"].
The first 4 words are ["Hello", "how", "are", "you"].
Hence, you should return "Hello how are you".

Example 2:

Input: s = "What is the solution to this problem", k = 4
Output: "What is the solution"
Explanation:
The words in s are ["What", "is" "the", "solution", "to", "this", "problem"].
The first 4 words are ["What", "is", "the", "solution"].
Hence, you should return "What is the solution".

Example 3:

Input: s = "chopper is not a tanuki", k = 5
Output: "chopper is not a tanuki"

Constraints:

1 <= s.length <= 500
k is in the range [1, the number of words in s].
s consist of only lowercase and uppercase English letters and spaces.
The words in s are separated by a single space.
There are no leading or trailing spaces.

Solution:

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

C++

class Solution {

public:

string truncateSentence(string s, int k) {

string ans;

stringstream ss(s);

for (int i = 0; i < k && ss; ++i) {

string word;

ss >> word;

ans += (ans.empty() ? "" : " ") + word;

}

return ans;

}

};

Python3

class Solution:

def truncateSentence(self, s: str, k: int) -> str:

return " ".join(s.split()[:k])

花花酱 LeetCode 1813. Sentence Similarity III

By zxi on April 3, 2021

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words consist of only uppercase and lowercase English letters.

Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. For example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in sentence2.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

Example 1:

Input: sentence1 = "My name is Haley", sentence2 = "My Haley"
Output: true
Explanation: sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".

Example 2:

Input: sentence1 = "of", sentence2 = "A lot of words"
Output: false
Explanation: No single sentence can be inserted inside one of the sentences to make it equal to the other.

Example 3:

Input: sentence1 = "Eating right now", sentence2 = "Eating"
Output: true
Explanation: sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.

Example 4:

Input: sentence1 = "Luky", sentence2 = "Lucccky"
Output: false

Constraints:

1 <= sentence1.length, sentence2.length <= 100
sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.
The words in sentence1 and sentence2 are separated by a single space.

Solution: Dequeue / Common Prefix + Suffix

Break sequences to words, store them in two deques. Pop the common prefix and suffix. At least one of the deque should be empty.

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

C++

// Author: Huahua

class Solution {

public:

bool areSentencesSimilar(string s1, string s2) {

auto getWords = [](const string& s) {

stringstream ss(s);

deque<string> words;

while (ss) {

words.emplace_back("");

ss >> words.back();

}

return words;

};

deque<string> w1 = getWords(s1), w2 = getWords(s2);

while (w1.size() && w2.size() && w1.front() == w2.front())

w1.pop_front(), w2.pop_front();

while (w1.size() && w2.size() && w1.back() == w2.back())

w1.pop_back(), w2.pop_back();

return w1.empty() || w2.empty();

}

};

Python3

# Author: Huahua

class Solution:

def areSentencesSimilar(self, s1: str, s2: str) -> bool:

w1 = deque(s1.split())

w2 = deque(s2.split())

while w1 and w2 and w1[0] == w2[0]:

w1.popleft(), w2.popleft()

while w1 and w2 and w1[-1] == w2[-1]:

w1.pop(), w2.pop()

return len(w1) * len(w2) == 0

花花酱 LeetCode 1812. Determine Color of a Chessboard Square

By zxi on April 3, 2021

You are given coordinates, a string that represents the coordinates of a square of the chessboard. Below is a chessboard for your reference.

Return true if the square is white, and false if the square is black.

The coordinate will always represent a valid chessboard square. The coordinate will always have the letter first, and the number second.

Example 1:

Input: coordinates = "a1"
Output: false
Explanation: From the chessboard above, the square with coordinates "a1" is black, so return false.

Example 2:

Input: coordinates = "h3"
Output: true
Explanation: From the chessboard above, the square with coordinates "h3" is white, so return true.

Example 3:

Input: coordinates = "c7"
Output: false

Constraints:

coordinates.length == 2
'a' <= coordinates[0] <= 'h'
'1' <= coordinates[1] <= '8'

Solution: Mod2

return (row_index + col_index) % 2 == 0

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

C++

class Solution {

public:

bool squareIsWhite(string coordinates) {

return ((coordinates[0] - 'a') + (coordinates[1] - '0')) % 2 == 0;

}

};

花花酱 LeetCode 1790. Check if One String Swap Can Make Strings Equal

By zxi on March 13, 2021

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Example 4:

Input: s1 = "abcd", s2 = "dcba"
Output: false

Constraints:

1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 and s2 consist of only lowercase English letters.

Solution: Remember two indices

There needs to be either 0 or 2 indices are different. Otherwise return false.
s1[idx1] == s2[idx2] and s1[idx2] == s2[idx1]

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

C++

// Author: Huahua

class Solution {

public:

bool areAlmostEqual(string s1, string s2) {

vector<int> idx;

for (int i = 0; i < s1.length() && idx.size() <= 2; ++i)

if (s1[i] != s2[i]) idx.push_back(i);

if (idx.size() == 0) return true;

if (idx.size() != 2) return false;

return s1[idx[0]] == s2[idx[1]] && s1[idx[1]] == s2[idx[0]];

}

};