Posts tagged as “medium”

花花酱 LeetCode 1247. Minimum Swaps to Make Strings Equal

By zxi on November 7, 2019

You are given two strings s1 and s2 of equal length consisting of letters "x" and "y" only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].

Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.

Example 1:

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: 
Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Example 2:

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: 
Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you can't swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.

Example 3:

Input: s1 = "xx", s2 = "xy"
Output: -1

Example 4:

Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
Output: 4

Constraints:

1 <= s1.length, s2.length <= 1000
s1, s2 only contain 'x' or 'y'.

Solution: Math

if s1[i] == s2[i] than no need to swap, so we can only look for
case1. s1[i] = x, s2[i] = y, xy
case2. s1[i] = y, s2[i] = x, yx

If case1 + case2 is odd, then there’s no solution.

Otherwise we can use one swap to fix two xys (or two yxs)
xx, yy => xy, yx

One special case is there an extra xy and and extra yx, which takes two swaps
xy, yx => yy, xx => xy, xy

Finally,
ans = (case1 + 1) / 2 + (case2 + 1) / 2

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

C++

// Author: Huahua

class Solution {

public:

int minimumSwap(string s1, string s2) {

int xy = 0;

int yx = 0;

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

if (s1[i] == 'x' && s2[i] == 'y') ++xy;

if (s1[i] == 'y' && s2[i] == 'x') ++yx;

}

if ((xy + yx) % 2) return -1;

return (xy + 1) / 2 + (yx + 1) / 2;

}

};

花花酱 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters

By zxi on October 27, 2019

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Constraints:

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lower case English letters.

Solution: Combination + Bit

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

C++

// Author: Huahua

class Solution {

public:

int maxLength(vector<string>& arr) {

vector<int> a;

for (const string& x : arr) {

set<char> s(begin(x), end(x));

if (s.size() != x.length()) continue;

a.push_back(0);

for (char c : x) a.back() |= 1 << (c - 'a');

}

int ans = 0;

function<void(int, int)> dfs = [&](int s, int cur) {

ans = max(ans, __builtin_popcount(cur));

for (int i = s; i < a.size(); ++i)

if ((cur & a[i]) == 0)

dfs(i + 1, cur | a[i]);

};

dfs(0, 0);

return ans;

}

};

Solution 2: DP

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

C++

// Author: Huahua

class Solution {

public:

int maxLength(vector<string>& arr) {

vector<int> a;

for (const string& x : arr) {

int mask = 0;

for (char c : x) mask |= 1 << (c - 'a');

if (__builtin_popcount(mask) != x.length()) continue;

a.push_back(mask);

}

int ans = 0;

vector<int> dp{0};

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

int size = dp.size();

for (int j = 0; j < size; ++j) {

if (dp[j] & a[i]) continue;

int t = dp[j] | a[i];

dp.push_back(t);

ans = max(ans, __builtin_popcount(t));

}

return ans;

}

};

花花酱 LeetCode 1238. Circular Permutation in Binary Representation

By zxi on October 27, 2019

Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1) such that :

p[0] = start
p[i] and p[i+1] differ by only one bit in their binary representation.
p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

Example 1:

Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:

Input: n = 3, start = 2
Output: [2,6,7,5,4,0,1,3]
Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

Constraints:

1 <= n <= 16
0 <= start < 2 ^ n

Solution 1: Gray Code (DP) + Rotation

Gray code starts with 0, need to rotate after generating the list.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> circularPermutation(int n, int start) {

vector<vector<int>> dp(n + 1);

dp[0] = {0};

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

dp[i] = dp[i - 1];

for (int j = dp[i - 1].size() - 1; j >= 0; --j)

dp[i].push_back(dp[i - 1][j] | (1 << (i - 1)));

}

for (auto it = begin(dp[n]); it != end(dp[n]); ++it)

if (*it == start) {

rotate(begin(dp[n]), it, end(dp[n]));

break;

}

return dp[n];

}

};

Solution 2: Gray code with a start

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

C++

// Author: Huahua

class Solution {

public:

vector<int> circularPermutation(int n, int start) {

vector<int> ans(1 << n);

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

ans[i] = start ^ i ^ i >> 1;

return ans;

}

};

花花酱 LeetCode 1233. Remove Sub-Folders from the Filesystem

By zxi on October 21, 2019

Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d/" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and ‘/’
folder[i] always starts with character ‘/’
Each folder name is unique.

Solution: HashTable

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

C++

// Author: Huahua

class Solution {

public:

vector<string> removeSubfolders(vector<string>& folder) {

unordered_set<string> s(begin(folder), end(folder));

vector<string> ans;

for (const auto& cur : folder) {

string f = cur;

bool valid = true;

while (!f.empty() && valid) {

while (f.back() != '/') f.pop_back();

f.pop_back();

if (s.count(f)) valid = false;

}

if (valid) ans.push_back(cur);

}

return ans;

}

};

花花酱 LeetCode 1223. Dice Roll Simulation

By zxi on October 17, 2019

A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.

Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls.

Two sequences are considered different if at least one element differs from each other. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.

Example 2:

Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30

Example 3:

Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

Constraints:

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

Solutions: DP

Naive one:

def: dp[i][j][k] := # of sequences ends with k consecutive j after i rolls
Init: dp[1][*][1] = 1

transition:
dp[i][j][1] = sum(dp[i-1][p][*]), p != j
dp[i][j][k + 1] = dp[i-1][j]][k]

Time complexity: O(n*6*6*15)
Space complexity: O(n*6*15) -> O(6*15)

C++

// Author: Huahua

class Solution {

public:

int dieSimulator(int n, vector<int>& rollMax) {

constexpr int kMaxRolls = 15;

constexpr int kMod = 1e9 + 7;

// dp[i][j][k] := # of sequences ends with k consecutive j after i rolls

vector<vector<vector<int>>> dp(n + 1,

vector<vector<int>>(6, vector<int>(kMaxRolls + 1)));

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

dp[1][j][1] = 1; // 1 step, 1 dice, 1 way

for (int i = 2; i <= n; ++i)

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

for (int p = 0; p < 6; ++p)

for (int k = 1; k <= rollMax[p]; ++k)

if (p != j) // not the same dice

dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k]) % kMod;

else if (k < rollMax[p]) // same dice, make sure k + 1 <= rollMax

dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][p][k]) % kMod;

int ans = 0;

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

for (int k = 1; k <= rollMax[j]; ++k)

ans = (ans + dp[n][j][k]) % kMod;

return ans;

}

};

Solution 2: DP with compressed state

dp[i][j] := # of sequences of length i end with j
dp[i][j] := sum(dp[i-1]) – invalid

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

C++

// Author: Huahua

class Solution {

public:

int dieSimulator(int n, vector<int>& rollMax) {

constexpr int kMod = 1e9 + 7;

// dp[i][j] := # of sequences ends with j after i rolls

vector<vector<int>> dp(n + 1, vector<int>(7));

vector<int> sums(n + 1); // sums[i] := sum(dp[i])

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

sums[1] += dp[1][j] = 1; // 1 roll, 1 dice, 1 way

for (int i = 2; i <= n; ++i)

for (int j = 0; j < 6; ++j) {

const int k = i - rollMax[j];

const int invalid = k <= 1 ? max(k, 0) : sums[k - 1] - dp[k - 1][j];

dp[i][j] = ((sums[i - 1] - invalid) % kMod + kMod) % kMod;

sums[i] = (sums[i] + dp[i][j]) % kMod;

}

return sums[n];

}

};