Posts tagged as “string”

花花酱 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating

By zxi on August 4, 2021

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

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.

Any two characters may be swapped, even if they are not adjacent.

Example 1:

Input: s = "111000"
Output: 1
Explanation: Swap positions 1 and 4: "111000" -> "101010"
The string is now alternating.

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating, no swaps are needed.

Example 3:

Input: s = "1110"
Output: -1

Constraints:

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

Solution: Greedy

Two passes, make the string starts with ‘0’ or ‘1’, count how many 0/1 swaps needed. 0/1 swaps must equal otherwise it’s impossible to swap.

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

C++

// Author: Huahua

class Solution {

public:

int minSwaps(string s) {

auto count = [&](int m) {

vector<int> swaps(2);

for (int i = 0; i < s.length(); ++i, m ^= 1)

if (s[i] - '0' != m)

++swaps[s[i] - '0'];

return swaps[0] == swaps[1] ? swaps[0] : INT_MAX;

};

int ans = min(count(0), count(1));

return ans != INT_MAX ? ans : -1;

}

};

花花酱 LeetCode 1859. Sorting the Sentence

By zxi on May 29, 2021

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

A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence.

For example, the sentence "This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3".

Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.

Example 1:

Input: s = "is2 sentence4 This1 a3"
Output: "This is a sentence"
Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.

Example 2:

Input: s = "Myself2 Me1 I4 and3"
Output: "Me Myself and I"
Explanation: Sort the words in s to their original positions "Me1 Myself2 and3 I4", then remove the numbers.

Constraints:

2 <= s.length <= 200
s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.
The number of words in s is between 1 and 9.
The words in s are separated by a single space.
s contains no leading or trailing spaces.

Solution: String

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

Python3

class Solution:

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

p = [(w[:-1], int(w[-1])) for w in s.split()]

p.sort(key=lambda x : x[1])

return " ".join((w for w, _ in p))

花花酱 LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

By zxi on May 8, 2021

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

For example, when num = "5489355142":
- The 1^st smallest wonderful integer is "5489355214".
- The 2^nd smallest wonderful integer is "5489355241".
- The 3^rd smallest wonderful integer is "5489355412".
- The 4^th smallest wonderful integer is "5489355421".

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.

The tests are generated in such a way that k^th smallest wonderful integer exists.

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4^th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355142" -> "5489355412"
- Swap index 8 with index 9: "5489355412" -> "5489355421"

Example 2:

Input: num = "11112", k = 4
Output: 4
Explanation: The 4^th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "11112" -> "11121"
- Swap index 2 with index 3: "11121" -> "11211"
- Swap index 1 with index 2: "11211" -> "12111"
- Swap index 0 with index 1: "12111" -> "21111"

Example 3:

Input: num = "00123", k = 1
Output: 1
Explanation: The 1^st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -> "00132"

Constraints:

2 <= num.length <= 1000
1 <= k <= 1000
num only consists of digits.

Solution: Next Permutation + Greedy

Time complexity: O(k*n + n^2)
Space complexity: O(n)

C++

class Solution {

public:

int getMinSwaps(string s, int k) {

string t(s);

while (k--) next_permutation(begin(t), end(t));

const int n = s.length();

int ans = 0;

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

if (s[i] == t[i]) continue;

for (int j = i + 1; j < n; ++j) {

if (s[i] != t[j]) continue;

ans += j - i;

t = t.substr(0, i + 1) + t.substr(i, j - i) + t.substr(j + 1);

break;

}

return ans;

}

};

花花酱 LeetCode 1844. Replace All Digits with Characters

By zxi on May 1, 2021

You are given a 0-indexed string s that has lowercase English letters in its even indices and digits in its odd indices.

There is a function shift(c, x), where c is a character and x is a digit, that returns the x^th character after c.

For example, shift('a', 5) = 'f' and shift('x', 0) = 'x'.

For every odd index i, you want to replace the digit s[i] with shift(s[i-1], s[i]).

Return s after replacing all digits. It is guaranteed that shift(s[i-1], s[i]) will never exceed 'z'.

Example 1:

Input: s = "a1c1e1"
Output: "abcdef"
Explanation: The digits are replaced as follows:
- s[1] -> shift('a',1) = 'b'
- s[3] -> shift('c',1) = 'd'
- s[5] -> shift('e',1) = 'f'

Example 2:

Input: s = "a1b2c3d4e"
Output: "abbdcfdhe"
Explanation: The digits are replaced as follows:
- s[1] -> shift('a',1) = 'b'
- s[3] -> shift('b',2) = 'd'
- s[5] -> shift('c',3) = 'f'
- s[7] -> shift('d',4) = 'h'

Constraints:

1 <= s.length <= 100
s consists only of lowercase English letters and digits.
shift(s[i-1], s[i]) <= 'z' for all odd indices i.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string replaceDigits(string s) {

for (size_t i = 1; i < s.length(); i += 2)

s[i] += s[i - 1] - '0';

return s;

}

};

花花酱 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;

}

};