Approach
Sorting and greedy selection
For ABC459 D — Adjacent Distinct String, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 67 lines of Python from the credited upstream file abc459_d.py.
- The implementation visibly relies on sequence storage, hash lookup.
- No explicit loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3from collections import Counter4from itertools import pairwise5 6 7def solve():8 s = input().rstrip()9 n = len(s)10 c = Counter(s)11 d = dict(sorted(c.items(), key=lambda x: x[1], reverse=True))12 keys = list(d.keys())13 14 for value in d.values():15 if value * 2 > (n + 1):16 return False, None17 18 ans = [""] * n19 pos = 020 21 for i in range(0, n, 2):22 key = keys[pos]23 24 if c[key] == 0:25 pos += 126 key = keys[pos]27 28 ans[i] = key29 c[key] -= 130 31 for i in range(1, n, 2):32 key = keys[pos]33 34 if c[key] == 0:35 pos += 136 key = keys[pos]37 38 ans[i] = key39 c[key] -= 140 41 for first, second in pairwise(ans):42 if first == second:43 return False, None44 45 return True, "".join(ans)46 47 48def main():49 import sys50 51 input = sys.stdin.readline52 53 t = int(input())54 55 for _ in range(t):56 ok, ans = solve()57 58 if ok:59 print("Yes")60 print(ans)61 else:62 print("No")63 64 65if __name__ == "__main__":66 main()67