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 sclass 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;
}
};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 = 16Output:
0Explanation:
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 = 37Output:
4Explanation:
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.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理