Smallest Number With No Adjacent Duplicates
You are given a string s containing "1", "2", "3" and "?". Given that you can replace any “?” with "1", "2" or "3", return the smallest number you can make as a string such that no two adjacent digits are the same.
Constraints
n ≤ 100,000wherenis the length ofs
https://binarysearch.com/problems/Smallest-Number-With-No-Adjacent-Duplicates
ExamplesPermalink
Example 1Permalink
Input
- s =
3?2??
Output
- answer =
31212
Example 2Permalink
Input
- s =
???
Output
- answer =
121
SolutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.*; | |
| class Solution { | |
| public String solve(String s) { | |
| String res = ""; | |
| for (int i = 0; i < s.length(); i++) { | |
| if (s.charAt(i) != '?') { | |
| res += s.charAt(i); | |
| continue; | |
| } | |
| boolean isOne = true; | |
| boolean isTwo = true; | |
| if (i > 0) { | |
| // all except first | |
| if (res.charAt(i - 1) == '1') | |
| isOne = false; | |
| if (res.charAt(i - 1) == '2') | |
| isTwo = false; | |
| } | |
| if (i < s.length() - 1) { | |
| // all except last | |
| if (s.charAt(i + 1) == '1') | |
| isOne = false; | |
| if (s.charAt(i + 1) == '2') | |
| isTwo = false; | |
| } | |
| if (isOne) | |
| res += '1'; | |
| else if (isTwo) | |
| res += '2'; | |
| else | |
| res += '3'; | |
| } | |
| return res; | |
| } | |
| } |
Leave a comment