algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

shortest-and-lexicographically-smallest-beautiful-string.cpp (2482B)

      1 class Solution {
      2 public:
      3     string shortestBeautifulSubstring(string s, int k) {
      4         // left = 0
      5         // right = 0
      6         // move right to right when num 1's < k
      7         // once num 1's == k track this if the length 
      8         // of this is < the shortest other string or if
      9         // it is the same size set it as the best if it's a smaller number than the other matching one
     10         // return once right == len(s)
     11 
     12         int left = 0;
     13         int right = 0;
     14         int oneCount = 0;
     15 
     16         if (s[0] == '1') {
     17             oneCount += 1;
     18         }
     19 
     20         int bestLeft = -1;
     21         int bestRight = -1;
     22 
     23         while(right < s.size()) {
     24             cout << oneCount << endl;
     25             if(oneCount < k) {
     26                 right += 1;
     27                 if (right < s.size() && s[right] == '1'){
     28                     oneCount += 1;
     29                 }
     30                 continue;
     31             }
     32             if(oneCount > k) {
     33                 left += 1;
     34                 if (left < s.size() && s[left - 1] == '1'){
     35                     oneCount -= 1;
     36                 }
     37                 continue;
     38             }
     39             if(oneCount == k) {
     40                 if(right - left < bestRight - bestLeft || bestRight + bestLeft == -2 || (right - left == bestRight - bestLeft && larger(bestLeft, bestRight, left, right, s))) {
     41                     bestLeft = left;
     42                     bestRight = right;
     43                 }
     44                 if(left + 1 <= right) {
     45                     left += 1;
     46                     if (left < s.size() && s[left - 1] == '1'){
     47                         oneCount -= 1;
     48                     }
     49                 } else {
     50                     right += 1;
     51                     if (right < s.size() && s[right] == '1'){
     52                         oneCount += 1;
     53                     }
     54                 }
     55 
     56                 continue;
     57             }
     58         }
     59 
     60         if(bestRight + bestLeft == -2) {
     61             return "";
     62         }
     63         string best = s.substr(bestLeft, (bestRight - bestLeft) + 1);
     64         return best;
     65 
     66 
     67     }
     68     private:
     69         bool larger(int bestLeft, int bestRight, int left, int right, string& s) {
     70             for(int i = 0; i < (bestRight - bestLeft) + 1; ++i) {
     71                 if(s[bestLeft + i] == '1' && s[left + i] == '0'){
     72                     return true;
     73                 }
     74                 if(s[bestLeft + i] == '0' && s[left + i] == '1'){
     75                     return false;
     76                 }
     77             }
     78             return true;
     79         }
     80 };