Zalando

01Longest String Without AAA or BBB

There are two-letter strings, "AA", "AB" and "BB", which appear AA, AB and BB times respectively. The task is to join some of these strings to create the longest possible string which does not contain "AAA" or "BBB". For example, having AA = 5, AB = 0 and BB = 2, it is possible to join five strings by taking both of the "BB" strings and three of the "AA" strings. Then they can be joined into "AA-BB-AA-BB-AA" = "AABBAABBA". Note that it is not possible to add another "AA" string as the result would then contain "AAA". Given three integers AA, AB and BB, returns the longest string that can be created according to the rules described above. If there is more than one possible answer, the function may return any of them.

Constraints

AA, AB and BB are integers within the range [0..10].
The resulting string will not be empty.

Example 1

Input:

AA = 5
AB = 0
BB = 2

Output:

"AABBAABBA"

Explanation: Given AA = 5, AB = 0 and BB = 2, the function should return "AABBAABBA", as explained above.

Example 2

Input:

AA = 1
AB = 2
BB = 1

Output:

"BBAABAA"

Explanation: Given AA = 1, AB = 2 and BB = 1, possible results are "BBAABAA", "ABABAB", "ABAABAB" or "AABBAAB".

Example 3

Input:

AA = 0
AB = 2
BB = 0

Output:

"ABAB"

Explanation: Given AA = 0, AB = 2 and BB = 0, the function should return "ABAB".

Example 4

Input:

AA = 0
AB = 0
BB = 10

Output:

"BB"

Explanation: Given AA = 0, AB = 0 and BB = 10, the function should return "BB".

解法

贪心：维护当前字符串末尾若是 'AA' 接 'BB'，若末尾是 'BB' 接 'AA'，否则取存量多的那一块。AB 全部排在前面(或最后)即可。这样保证三连不出现。时间 O(AA+AB+BB)。

def longest_string(AA: int, AB: int, BB: int) -> str:
    out: list = []
    # alternate "AA" and "BB"; pick whichever has more
    while AA > 0 or BB > 0:
        if AA > BB:
            out.append("AA"); AA -= 1
            if BB > 0:
                out.append("BB"); BB -= 1
        elif BB > AA:
            out.append("BB"); BB -= 1
            if AA > 0:
                out.append("AA"); AA -= 1
        else:
            if AA > 0:
                out.append("AA"); AA -= 1
            if BB > 0:
                out.append("BB"); BB -= 1
    return "".join(out) + "AB" * AB

class Solution {
    public String longestString(int AA, int AB, int BB) {
        StringBuilder sb = new StringBuilder();
        while (AA > 0 || BB > 0) {
            if (AA > BB) { sb.append("AA"); AA--; if (BB > 0) { sb.append("BB"); BB--; } }
            else if (BB > AA) { sb.append("BB"); BB--; if (AA > 0) { sb.append("AA"); AA--; } }
            else { if (AA > 0) { sb.append("AA"); AA--; } if (BB > 0) { sb.append("BB"); BB--; } }
        }
        for (int i = 0; i < AB; i++) sb.append("AB");
        return sb.toString();
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string longestString(int AA, int AB, int BB) {
        string s;
        while (AA > 0 || BB > 0) {
            if (AA > BB) { s += "AA"; AA--; if (BB > 0) { s += "BB"; BB--; } }
            else if (BB > AA) { s += "BB"; BB--; if (AA > 0) { s += "AA"; AA--; } }
            else { if (AA > 0) { s += "AA"; AA--; } if (BB > 0) { s += "BB"; BB--; } }
        }
        for (int i = 0; i < AB; i++) s += "AB";
        return s;
    }
};

02Zalando Manipulation

A string S consisting of the letters A, B, C and D is given. The string can be transformed either by removing a letter A together with an adjacent letter B, or by removing a letter C together with an adjacent letter D. Write a function: class Solution { public String solution(String S); } that, given a string S consisting of N characters, returns any string that:

can be obtained from S by repeatedly applying the described transformation, and
cannot be further transformed. If at some point there is more than one possible way to transform the string, any of the valid transformations may be chosen. Write an efficient algorithm for the following assumptions:
the length of string S is within the range [0..250,000];
string S is made only of the following characters: 'A', 'B', 'C' and/or 'D'.

Example 1

Input:

S = "CBACD"

Output:

"C"

Explanation: One of the possible sequences of operations is as follows:

CBACD → CCD → C

Example 2

Input:

S = "CABABD"

Output:

""

Explanation: One possible sequence of operations is:

CABABD → CDD → ""

Example 3

Input:

S = "ACBDACBD"

Output:

"ACBDACBD"

Explanation: No operation can be applied to string S, so the function should return "ACBDACBD".

解法

栈消除(同 Jane Street)：遇 AB/BA/CD/DC 出栈，否则入栈。时间 O(N)。

def solution(S: str) -> str:
    pairs = {("A", "B"), ("B", "A"), ("C", "D"), ("D", "C")}
    stack: list = []
    for c in S:
        if stack and (stack[-1], c) in pairs:
            stack.pop()
        else:
            stack.append(c)
    return "".join(stack)

class Solution {
    public String solution(String S) {
        StringBuilder st = new StringBuilder();
        for (char c : S.toCharArray()) {
            int n = st.length();
            if (n > 0) {
                char t = st.charAt(n - 1);
                if ((t == 'A' && c == 'B') || (t == 'B' && c == 'A') || (t == 'C' && c == 'D') || (t == 'D' && c == 'C')) {
                    st.deleteCharAt(n - 1); continue;
                }
            }
            st.append(c);
        }
        return st.toString();
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string solution(string S) {
        string st;
        for (char c : S) {
            if (!st.empty()) {
                char t = st.back();
                if ((t == 'A' && c == 'B') || (t == 'B' && c == 'A') || (t == 'C' && c == 'D') || (t == 'D' && c == 'C')) { st.pop_back(); continue; }
            }
            st += c;
        }
        return st;
    }
};