Created
July 22, 2022 02:26
-
-
Save harryWonder/dec643da07ba7ee38db2465e88d639bf to your computer and use it in GitHub Desktop.
This code snippet helps us to partition a string into several partitions. The total sum of the groups should equal the total length of the string and each of the alphabets in each group should be unique
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
/** | |
* Given a string, break the string down in such a way that the total group of the strings equals the total length of the string. | |
* Each alphabets should be unique in the group as well. | |
*/ | |
const Alphabets = "abcdefghijklmnopqrstuvwxyz"; | |
/** | |
* Use recursion to solve | |
* @param {string} input | |
* @param {string} nextLetter | |
* | |
*/ | |
function PartitionLabels(input = "ababcbacadefegdehijhklij", groups = [], firstAlphabet = null) { | |
let firstLetter = firstAlphabet == null ? input[0] : firstAlphabet; | |
let firstLetterLastPosition = input.lastIndexOf(firstLetter) + 1; | |
/* get the first group */ | |
let firstGroup = input.substring(0, input.lastIndexOf(firstLetter) + 1); | |
let otherGroup = input.split(firstGroup)[1]; | |
let firstGroupArray = [...firstGroup]; | |
let actualIndex = firstGroupArray.map((el) => { | |
if (otherGroup.includes(el)) { | |
/* E was found here so re-calculate */ | |
return otherGroup.lastIndexOf(el); | |
} | |
}).filter(el => el != undefined); | |
if (actualIndex.length == 0) { | |
/* Push the index */ | |
groups.push(firstLetterLastPosition); | |
if (otherGroup.length > 0) { | |
PartitionLabels(otherGroup, groups); | |
} | |
} else if (actualIndex.length > 0) { | |
firstLetter = otherGroup[Math.max(...actualIndex)]; | |
if (firstLetter.length > 0) { | |
firstLetter = firstLetter[0]; | |
} else { | |
firstLetter = actualIndex[actualIndex.length - 1]; | |
} | |
/* Get duplicates value index */ | |
nextGroup = input.substring(input.lastIndexOf(firstLetter) + 1, input.length); | |
/* Modification Code */ | |
let initialInputGroup = input.substring(0, input.length - nextGroup.length); | |
let nextGroupArray = [...nextGroup]; | |
let nextGroupDuplicateCheck = nextGroupArray.map((el) => { | |
if (initialInputGroup.includes(el)) { | |
return el; | |
} | |
}).filter((el) => el != undefined); | |
if (nextGroupDuplicateCheck.length > 0) { | |
return PartitionLabels(input, groups, nextGroupDuplicateCheck[nextGroupDuplicateCheck.length - 1]); | |
} else { | |
if (!nextGroup.includes(firstLetter)) { | |
groups.push(input.lastIndexOf(firstLetter) + 1); | |
if (nextGroup) { | |
PartitionLabels(nextGroup, groups); | |
} | |
} | |
} | |
} | |
if (groups.reduce((a, b) => a + b) == input.length) { | |
console.log(groups); | |
return groups; | |
} | |
} | |
PartitionLabels("ababcbacadefegdehijhklij", []); | |
PartitionLabels("eccbbbbdec", []); | |
PartitionLabels("bceacbacdbbadea", []); | |
PartitionLabels("caedbdedda", []); | |
PartitionLabels("eaedcaaadedaacb", []); | |
PartitionLabels("qiejxqfnqceocmy", []); | |
// console.log(groups); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment