Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Problem Statement: You'll be given two strings A and B, with lengths 1 <= length <= 10^6. The strings will contain only 1's and 0's. To make A a good string, you can insert B into A at any place, as many times as you want (or don't insert if you don't want). You have to print YES or NO depending on whether making A as a good string is possible.
- The Definition of GOOD: A good string will never consecutively have two 1's or two 0's.
- */
- interface EvaluationResult {
- has00: boolean,
- has11: boolean,
- isGood: boolean,
- isBeyondSaving: boolean
- }
- function evaluateString(str: string): EvaluationResult {
- let has00 = false;
- let has11 = false;
- for (let i = 1; i < str.length; ++i) {
- if (str[i] === str[i - 1]) {
- // bad string
- if (str[i] === "0") {
- has00 = true;
- }
- else {
- has11 = true;
- }
- }
- }
- return {
- has00,
- has11,
- isGood: !has00 && !has11,
- isBeyondSaving: has00 && has11
- };
- }
- function canStringBeMadeGood(strA: string, strB: string): "YES" | "NO" {
- // TODO: maybe handle empty string case
- const strAResult = evaluateString(strA);
- if (strAResult.isGood) {
- return "YES";
- }
- if (strAResult.isBeyondSaving) {
- return "NO";
- }
- const strBResult = evaluateString(strB);
- if (!strBResult.isGood) {
- return "NO";
- }
- if (strAResult.has00 && strB.startsWith("1") && strB.endsWith("1")) {
- return "YES";
- }
- if (strAResult.has11 && strB.startsWith("0") && strB.endsWith("0")) {
- return "YES";
- }
- return "NO";
- }
- console.log(canStringBeMadeGood("101", "010")); // YES
- console.log(canStringBeMadeGood("111", "010")); // YES
- console.log(canStringBeMadeGood("1110011", "01010")); // NO
- console.log(canStringBeMadeGood("1001001000", "10")); // NO
Advertisement
Add Comment
Please, Sign In to add comment