_3211.java

packagecom.fishercoder.solutions.fourththousand;

importjava.util.ArrayList;
importjava.util.HashSet;
importjava.util.List;
importjava.util.Set;

publicclass_3211 {
publicstaticclassSolution1 {
publicList<String> validStrings(intn) {
List<String> result = newArrayList<>();
for (inti = n / 2; i <= n; i++) {
List<String> combinations = generateCombinations(i, n - i);
for (Strings : combinations) {
if (noAdjacentZeroes(s)) {
result.add(s);
 }
 }
 }
returnresult;
 }

privatebooleannoAdjacentZeroes(Strings) {
for (inti = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == '0' && s.charAt(i + 1) == '0') {
returnfalse;
 }
 }
returntrue;
 }

privateList<String> generateCombinations(intones, intzeroes) {
int[] nums = newint[ones + zeroes];
inti = 0;
while (ones-- > 0) {
nums[i++] = 1;
 }
returnpermuteUnique(nums);
 }

privateList<String> permuteUnique(int[] nums) {
Set<String> set = newHashSet<>();
set.add("");
set = recurse(nums, set, 0);
List<String> list = newArrayList<>();
for (Strings : set) {
list.add(s);
 }
returnlist;
 }

privateSet<String> recurse(int[] nums, Set<String> set, intpos) {
if (pos == nums.length) {
returnset;
 }
Set<String> newSet = newHashSet<>();
for (Strings : set) {
for (inti = 0; i <= s.length(); i++) {
StringBuildersb = newStringBuilder(s);
sb.insert(i, nums[pos]);
newSet.add(sb.toString());
 }
 }
returnrecurse(nums, newSet, pos + 1);
 }
 }
}