Deutsche Bank

01Generate Lexicographically Smallest String

String S1 of length L1 consisting of uppercase alphabets only. String S2 of length L2 consisting of characters 'T' and 'F' only. Generate a lexicographically smallest string S of length (L1 + L2 - 1) such that a substring of length L1 in string S starting at index (0 ≤ i < L2) is equal to S1 if and only if ith element of S2 is 'T'. If generating a string is not possible return -1.

Constraints

1 ≤ L1 ≤ 10⁴
1 ≤ L2 ≤ 100

Example 1

Input:

S1 = "ABCA"
S2 = "TFFF"

Output:

"ABCAAAA"

Explanation: S="ABCAAAA" is lexicographically smallest string that satisfies the given condition:-

Character at index 0 of S2 = 'T' and Substring starting at index 0: "ABCA" is equal to S1.
Character at index 1 of S2 = 'F'
Character at index 2 of S2 = 'F'
Character at index 3 of S2 = 'F'

Example 2

Input:

S1 = "ABA"
S2 = "TFT"

Output:

"ABABA"

Explanation: S="ABABA" is the lexicographically smallest string that satisfies the given condition.

Example 3

Input:

S1 = "ABC"
S2 = "TFT"

Output:

"-1"

Explanation: It is not possible to generate a string that satisfies the given condition, hence the output is -1.

解法

每个 T 位 i 强制 S[i..i+L1-1] = S1。先把所有 T 位强制写入 S(长度 L1+L2-1)，若两次强制写入冲突则返回 -1。剩下的位置填 A(最小字母)使整体字典序最小。最后再校验所有 F 位对应的 L1 长度子串都不等于 S1(否则违反 only if 条件，返回 -1)。时间 O((L1+L2)·L1)。

def generate_smallest(S1: str, S2: str):
    L1, L2 = len(S1), len(S2)
    N = L1 + L2 - 1
    S = ['?'] * N
    for i, c in enumerate(S2):
        if c == 'T':
            for k in range(L1):
                if S[i + k] != '?' and S[i + k] != S1[k]:
                    return "-1"
                S[i + k] = S1[k]
    for i in range(N):
        if S[i] == '?':
            S[i] = 'A'
    s = "".join(S)
    for i, c in enumerate(S2):
        if c == 'F' and s[i:i + L1] == S1:
            return "-1"
    return s

class Solution {
    public String generateSmallest(String S1, String S2) {
        int L1 = S1.length(), L2 = S2.length(), N = L1 + L2 - 1;
        char[] S = new char[N];
        Arrays.fill(S, '?');
        for (int i = 0; i < L2; i++) {
            if (S2.charAt(i) == 'T') {
                for (int k = 0; k < L1; k++) {
                    if (S[i + k] != '?' && S[i + k] != S1.charAt(k)) return "-1";
                    S[i + k] = S1.charAt(k);
                }
            }
        }
        for (int i = 0; i < N; i++) if (S[i] == '?') S[i] = 'A';
        String s = new String(S);
        for (int i = 0; i < L2; i++) {
            if (S2.charAt(i) == 'F' && s.startsWith(S1, i)) return "-1";
        }
        return s;
    }
}

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

class Solution {
public:
    string generateSmallest(string S1, string S2) {
        int L1 = S1.size(), L2 = S2.size(), N = L1 + L2 - 1;
        string S(N, '?');
        for (int i = 0; i < L2; i++) {
            if (S2[i] == 'T') {
                for (int k = 0; k < L1; k++) {
                    if (S[i + k] != '?' && S[i + k] != S1[k]) return "-1";
                    S[i + k] = S1[k];
                }
            }
        }
        for (auto& c : S) if (c == '?') c = 'A';
        for (int i = 0; i < L2; i++) {
            if (S2[i] == 'F' && S.compare(i, L1, S1) == 0) return "-1";
        }
        return S;
    }
};

02Give Minimum Sum

Give the minimum sum of (x+y) such that A and B are given and (A+x) should be multiple of (B+y).

Example 1

Input:

A = 8
B = 16

Output:

Explanation: Educated guess - Since A is already a multiple of B, no additional sum is needed. Therefore, the answer is 0.

Example 2

Input:

A = 7
B = 37

Output:

Explanation: Educated guess - The minimum sum of (x+y) to make (A+x) a multiple of (B+y) is 4. This can be achieved by setting x = 3 and y = 1, making (A+x) = 10 and (B+y) = 38, where 10 is a multiple of 38.

解法

求最小 x+y(x, y ≥ 0)，使 (A+x) % (B+y) == 0。枚举 B+y 的取值 m：x 必须使 A+x 是 m 的倍数。给定 m，最小的 x 满足：若 A % m == 0 则 x=0，否则 x = m - A % m。同时 y = m - B(需 ≥0)。从 m=B 开始向上枚举，第一个使 x+y ≤ 当前最优 的就够；上界控制为 min(2A, 2B) 之类即可。注意 m=1 也合法(任何数都是 1 的倍数)，但需 y = 1-B；只有 B=1 时才合法。整体策略：枚举 m∈[max(1,B), A+B] 即可，时间 O(A+B)。

def give_minimum_sum(A: int, B: int) -> int:
    best = float('inf')
    # m = B + y, m >= B (since y >= 0)
    upper = max(A, B) + max(A, B) + 2
    for m in range(B, upper + 1):
        y = m - B
        x = 0 if A % m == 0 else (m - A % m)
        best = min(best, x + y)
        if best == 0:
            break
    return int(best)

class Solution {
    public int giveMinimumSum(int A, int B) {
        int best = Integer.MAX_VALUE;
        int upper = Math.max(A, B) * 2 + 2;
        for (int m = B; m <= upper; m++) {
            int y = m - B;
            int x = (A % m == 0) ? 0 : (m - A % m);
            best = Math.min(best, x + y);
            if (best == 0) break;
        }
        return best;
    }
}

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

class Solution {
public:
    int giveMinimumSum(int A, int B) {
        int best = INT_MAX;
        int upper = max(A, B) * 2 + 2;
        for (int m = B; m <= upper; m++) {
            int y = m - B;
            int x = (A % m == 0) ? 0 : (m - A % m);
            best = min(best, x + y);
            if (best == 0) break;
        }
        return best;
    }
};