Determine whether the bugs can be rearranged so that every bug is happy, or if the current arrangement is already valid.
Problem
You are given a string describing a line of ladybugs. Each character is either an uppercase English letter representing a colored ladybug or an underscore _ representing an empty cell.
A ladybug is happy if at least one of its adjacent cells contains a ladybug of the same color. Adjacent means left or right, when those cells exist.
You may move ladybugs only into empty cells. The goal is to determine whether it is possible to rearrange the ladybugs so that every ladybug becomes happy.
Return whether such a rearrangement is possible.
Notes
- Empty cells may be used to move ladybugs around.
- If a color appears only once, that ladybug can never become happy.
- If there are no empty cells, the current arrangement must already satisfy the happiness condition.
Input Format
- The first line contains an integer — the number of test cases.
- Each of the next lines contains a string consisting of uppercase English letters and underscores
_.
Output Format
For each test case, print YES if it is possible to rearrange the ladybugs so that every ladybug is happy, otherwise print NO.
Constraints
- is typical for multiple test cases.
- contains only uppercase English letters and
_. - The exact platform constraints are not required here; use the logic above.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.