Posts tagged as “string”

花花酱 LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts

By zxi on March 8, 2020

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’ must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

Constraints:

1 <= s.length <= 5 x 10^5
s contains only lowercase English letters.

Solution: HashTable

Record the first index when a state occurs. index – last_index is the length of the all-even-vowel substring.

State: {a: odd|even, e: odd|even, …, u:odd|even}.

There are total 2^5 = 32 states that can be represented as a binary string.

whenever a vowel occurs, we flip the bit, e.g. odd->even, even->odd using XOR.

Time complexity: O(5*n)
Space complexity: O(32)

C++

// Author: Huahua

class Solution {

public:

int findTheLongestSubstring(string s) {

const char vowels[] = "aeiou";

vector<int> idx(1 << 5, INT_MAX); // state -> first_index

idx[0] = -1;

int state = 0;

int ans = 0;

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

for (int j = 0; j < 5; ++j)

if (s[i] == vowels[j]) state ^= 1 << j;

if (idx[state] == INT_MAX) idx[state] = i;

ans = max(ans, i - idx[state]);

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

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

idx = {0 : -1}

vowels = "aeiou"

state = 0

ans = 0

for i in range(len(s)):

j = vowels.find(s[i])

if j >= 0: state ^= 1 << j

if state not in idx:

idx[state] = i

ans = max(ans, i - idx[state])

return ans

花花酱 LeetCode 1370. Increasing Decreasing String

By zxi on March 7, 2020

Given a string s. You should re-order the string using the following algorithm:

Pick the smallest character from s and append it to the result.
Pick the smallest character from s which is greater than the last appended character to the result and append it.
Repeat step 2 until you cannot pick more characters.
Pick the largest character from s and append it to the result.
Pick the largest character from s which is smaller than the last appended character to the result and append it.
Repeat step 5 until you cannot pick more characters.
Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

Example 2:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

Example 3:

Input: s = "leetcode"
Output: "cdelotee"

Example 4:

Input: s = "ggggggg"
Output: "ggggggg"

Example 5:

Input: s = "spo"
Output: "ops"

Constraints:

1 <= s.length <= 500
s contains only lower-case English letters.

Solution: Counting frequency of each character

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

C++

// Author: Huahua

class Solution {

public:

string sortString(string s) {

vector<int> count(26);

for (char c : s) ++count[c - 'a'];

string ans;

while (ans.length() != s.length()) {

for (char c = 'a'; c <= 'z'; ++c)

if (--count[c - 'a'] >= 0)

ans += c;

for (char c = 'z'; c >= 'a'; --c)

if (--count[c - 'a'] >= 0)

ans += c;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def sortString(self, s: str) -> str:

seq = string.ascii_lowercase + string.ascii_lowercase[::-1]

count = collections.Counter(s)

ans = ""

while len(ans) != len(s):

for c in seq:

if count[c] > 0:

ans += c

count[c] -= 1

return ans

花花酱 LeetCode 1328. Break a Palindrome

By zxi on January 26, 2020

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome.

After doing so, return the final string. If there is no way to do so, return the empty string.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"

Example 2:

Input: palindrome = "a"
Output: ""

Constraints:

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.

Solution: Greedy

For the first half of the string, replace the first non ‘a’ character to ‘a’.

e.g. abcdcba => aacdcba

If not found which means the the entire string is ‘a’ expect the middle one if the length is odd, like aa or aba, replace the last character to ‘b’.

aa => ab
aba => abb

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

C++

// Author: Huahua

class Solution {

public:

string breakPalindrome(string palindrome) {

const int n = palindrome.length();

if (n == 1) return "";

for (int i = 0; i < n / 2; ++i) {

if (palindrome[i] != 'a') {

palindrome[i] = 'a';

return palindrome;

}

palindrome.back() = 'b';

return palindrome;

}

};

花花酱 LeetCode 1323. Maximum 69 Number

By zxi on January 20, 2020

Given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666. 
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Constraints:

1 <= num <= 10^4
num‘s digits are 6 or 9.

Solution: Greedy

Replace the highest 6 to 9, if no 6, return the original number.

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

C++

// Author: Huahua

class Solution {

public:

int maximum69Number (int num) {

string s = to_string(num);

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

if (s[i] == '6') {

s[i] = '9';

return stoi(s);

}

return num;

}

};

花花酱 LeetCode 1316. Distinct Echo Substrings

By zxi on January 11, 2020

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself.

Example 1:

Input: text = "abcabcabc"
Output: 3
Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".

Example 2:

Input: text = "leetcodeleetcode"
Output: 2
Explanation: The 2 substrings are "ee" and "leetcodeleetcode".

Constraints:

1 <= text.length <= 2000
text has only lowercase English letters.

Solution 1: Brute Force + HashSet

Try all possible substrings

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

C++

// Author: Huahua

class Solution {

public:

int distinctEchoSubstrings(string text) {

const int n = text.length();

string_view t(text);

unordered_set<string_view> s;

for (int k = 1; k <= n / 2; ++k)

for (int i = 0; i + k <= n; ++i)

if (t.substr(i, k) == t.substr(i + k, k))

s.insert(t.substr(i, 2 * k));

return s.size();

}

};