Huahua’s Tech Road

花花酱 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 1237. Find Positive Integer Solution for a Given Equation

By zxi on October 27, 2019

Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.

The function is constantly increasing, i.e.:

f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)

The function interface is defined like this:

interface CustomFunction {
public:
  // Returns positive integer f(x, y) for any given positive integer x and y.
  int f(int x, int y);
};

For custom testing purposes you’re given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you’ll know only two functions from the list.

You may return the solutions in any order.

Example 1:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y

Example 2:

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y

Constraints:

1 <= function_id <= 9
1 <= z <= 100
It’s guaranteed that the solutions of f(x, y) == z will be on the range 1 <= x, y <= 1000
It’s also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000

Solution1 : Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {

vector<vector<int>> ans;

for (int x = 1; x <= 1000; ++x) {

if (customfunction.f(x, 1) > z) break;

for (int y = 1; y <= 1000; ++y) {

int t = customfunction.f(x, y);

if (t > z) break;

if (t == z) ans.push_back({x, y});

}

return ans;

}

};

花花酱 LeetCode 1240. Tiling a Rectangle with the Fewest Squares

By zxi on October 27, 2019

Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

Solution1: DP + Cheating

DP can not handle case 3, for m, n <= 13, (11,13) is the only case of that special case.

dp[i][j] := min squares to tile a i x j rectangle.

dp[i][i] = 1

dp[i][j] = min(dp[r][j] + dp[i-r][j], dp[i][c] + dp[i][j – c]), 1 <= r <= i/2, 1 <= c <= j /2

answer dp[m][n]

Time complexity: O(m*n*max(n, m))
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int tilingRectangle(int n, int m) {

if (max(n, m) == 13 && min(n, m) == 11) return 6;

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

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

for (int j = 1; j <= m; ++j) {

dp[i][j] = INT_MAX;

if (i == j) {

dp[i][j] = 1;

continue;

}

for (int r = 1; r <= i / 2; ++r)

dp[i][j] = min(dp[i][j], dp[r][j] + dp[i - r][j]);

for (int c = 1; c <= j / 2; ++c)

dp[i][j] = min(dp[i][j], dp[i][c] + dp[i][j - c]);

}

return dp[n][m];

}

};

Solution 2: DFS

C++

// Author: Huahua

class Solution {

public:

int tilingRectangle(int n, int m) {

if (n > m) return tilingRectangle(m, n);

int ans = n * m;

vector<int> h(n);

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

if (cur >= ans) return;

auto it = min_element(begin(h), end(h));

if (*it == m) { // All filled

ans = cur;

return;

}

int low = *it;

int s = it - begin(h);

int e = s;

// Find the base

while (e < n && h[e] == h[s] && (e - s + 1 + low) <= m) ++e;

for (int i = --e; i >= s; --i) {

// Try all possible square sizes in reverse order.

int size = i - s + 1;

for (int j = s; j <= i; ++j) h[j] += size;

dfs(cur + 1);

for (int j = s; j <= i; ++j) h[j] -= size;

}

};

dfs(0);

return ans;

}

};

Huahua's Tech Road

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

Solution: Math

C++

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

Solution: Combination + Bit

C++

C++

花花酱 LeetCode 1238. Circular Permutation in Binary Representation

C++

Solution 2: Gray code with a start

C++

花花酱 LeetCode 1237. Find Positive Integer Solution for a Given Equation

Solution1 : Brute Force

C++

花花酱 LeetCode 1240. Tiling a Rectangle with the Fewest Squares

Solution1: DP + Cheating

C++

Solution 2: DFS

C++