Posts tagged as “string”

花花酱 LeetCode 1869. Longer Contiguous Segments of Ones than Zeros

By zxi on August 5, 2021

Given a binary string s, return true if the longest contiguous segment of 1s is strictly longer than the longest contiguous segment of 0s in s. Return false otherwise.

For example, in s = "110100010" the longest contiguous segment of 1s has length 2, and the longest contiguous segment of 0s has length 3.

Note that if there are no 0s, then the longest contiguous segment of 0s is considered to have length 0. The same applies if there are no 1s.

Example 1:

Input: s = "1101"
Output: true
Explanation:
The longest contiguous segment of 1s has length 2: "1101"
The longest contiguous segment of 0s has length 1: "1101"
The segment of 1s is longer, so return true.

Example 2:

Input: s = "111000"
Output: false
Explanation:
The longest contiguous segment of 1s has length 3: "111000"
The longest contiguous segment of 0s has length 3: "111000"
The segment of 1s is not longer, so return false.

Example 3:

Input: s = "110100010"
Output: false
Explanation:
The longest contiguous segment of 1s has length 2: "110100010"
The longest contiguous segment of 0s has length 3: "110100010"
The segment of 1s is not longer, so return false.

Constraints:

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

Solution: Brute Force

Write a function count to count longest contiguous segment of m, return count(‘1’) > count(‘0’)

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

C++

// Author: Huahua

class Solution {

public:

bool checkZeroOnes(string s) {

auto count = [&](char m) {

int ans = 0;

int l = 0;

for (char c : s)

if (c != m) l = 0;

else ans = max(ans, ++l);

return ans;

};

return count('1') > count('0');

}

};

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

}

};