fueanta

Is string good or can be made good

May 17th, 2026 (edited)
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. 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.
  3.  
  4. The Definition of GOOD: A good string will never consecutively have two 1's or two 0's.
  5.  */
  6.  
  7. interface EvaluationResult {
  8.     has00:          boolean,
  9.     has11:          boolean,
  10.     isGood:         boolean,
  11.     isBeyondSaving: boolean
  12. }
  13.  
  14. function evaluateString(str: string): EvaluationResult {
  15.     let has00 = false;
  16.     let has11 = false;
  17.  
  18.     for (let i = 1; i < str.length; ++i) {
  19.         if (str[i] === str[i - 1]) {
  20.             // bad string
  21.             if (str[i] === "0") {
  22.                 has00 = true;
  23.             }
  24.             else {
  25.                 has11 = true;
  26.             }
  27.         }
  28.     }
  29.  
  30.     return {
  31.         has00,
  32.         has11,
  33.         isGood:         !has00 && !has11,
  34.         isBeyondSaving: has00 && has11
  35.     };
  36. }
  37.  
  38. function canStringBeMadeGood(strA: string, strB: string): "YES" | "NO" {
  39.     // TODO: maybe handle empty string case
  40.     const strAResult = evaluateString(strA);
  41.  
  42.     if (strAResult.isGood) {
  43.         return "YES";
  44.     }
  45.  
  46.     if (strAResult.isBeyondSaving) {
  47.         return "NO";
  48.     }
  49.  
  50.     const strBResult = evaluateString(strB);
  51.  
  52.     if (!strBResult.isGood) {
  53.         return "NO";
  54.     }
  55.  
  56.     if (strAResult.has00 && strB.startsWith("1") && strB.endsWith("1")) {
  57.         return "YES";
  58.     }
  59.  
  60.     if (strAResult.has11 && strB.startsWith("0") && strB.endsWith("0")) {
  61.         return "YES";
  62.     }
  63.  
  64.     return "NO";
  65. }
  66.  
  67. console.log(canStringBeMadeGood("101", "010"));       // YES
  68. console.log(canStringBeMadeGood("111", "010"));       // YES
  69. console.log(canStringBeMadeGood("1110011", "01010")); // NO
  70. console.log(canStringBeMadeGood("1001001000", "10")); // NO
Advertisement
Add Comment
Please, Sign In to add comment