leetcode: Strong Password Checker.cpp

    
struct Seq {
  size_t start, size;
};

ostream& operator<<(ostream& os, const Seq& s) {
  return os << "[" << s.start << ", " << s.size << ")";
}

// Returns the number of replacements or additions required to break sequences to have no triplets.
unsigned int breakByReplacementOrAddition(const std::vector<Seq>& v) {
  unsigned int sum = 0;
  for (const Seq& s : v) sum += s.size / 3;
  return sum;
}

// Returns the number of subtractions required to break sequences to have no triplets.
unsigned int breakBysubtraction(std::vector<Seq>& v, size_t& max_subtractions) {
  unsigned int sum = 0;
  
  while (max_subtractions && v.size()) {
    // Find the smallest sequence we can shrink. If we can get that sequence below the threshhold,
    // that's one less sequence we'll need to do a replacement on so this minimizes edits.
    auto it = std::min_element(v.begin(), v.end(), [](const Seq& a, const Seq& b) { return a.size < b.size; });
    cout << "seq: [" << it->start << ", " << it->size << ")\n";
    cout << "want to remove " << (it->size - (it->size - 2)) << " out of " << max_subtractions << endl;
    size_t rm = std::min(it->size - (it->size - 2), max_subtractions);
    max_subtractions -= rm;
    it->size -= rm;
    sum += rm;
    
    if (it->size < 3) v.erase(it);
  }
  return sum;
}

class Solution {
public:
  // The size requirement makes this problem hard.
  // say MIN = 1 and MAX = 3.
  // aaab is bad because it contains too many letters (errors++) and repeats (errors++),
  // but only one change (delete an 'a') is required to fix it.
  // 
  // Idea: Count the number of repeats and if one of those letters could become a different
  //       case and no letter of that case yet exists, or a digit and no digit exists, it's too long, etc.,
  //       reduce the changes needed by one. Do a similar thing if too long.
  //
  //       Watch out for logic that would want to change a letter's case AND make it a number.
  int strongPasswordChecker(string s) {
    int changes_needed = 0;
    
    // Storing the binary requirements in a list will allow us to iterate over them instead of long if (no_digit) { ... } if (no_upper) { ..} chains.
    enum Requirements { HAS_LOWER, HAS_UPPER, HAS_DIGIT };
    bool reqs[] = {false, false, false};
    
    std::vector<Seq> contiguous_repeats;
    Seq last_repeat_seq = {string::npos, 0};
    char last_char = 0;  // We assume null is not in the inputs.
    size_t last_triplet_pos = string::npos;
    for (size_t i = 0; i < s.size(); i++) {
      if ('a' <= s[i] && s[i] <= 'z') reqs[HAS_LOWER] = true;
      if ('A' <= s[i] && s[i] <= 'Z') reqs[HAS_UPPER] = true;
      if ('0' <= s[i] && s[i] <= '9') reqs[HAS_DIGIT] = true;
      if (s[i] == last_char) {
        last_repeat_seq.size++;
      } else {
        if (last_repeat_seq.size > 2) {
          contiguous_repeats.push_back(last_repeat_seq);
          //cout << "adding contiguous seq: [" << last_repeat_seq.start << ", " << last_repeat_seq.size << ")\n";
        }
        last_repeat_seq.start = i;
        last_repeat_seq.size = 1;
        
        last_char = s[i];
        
        //cout << "new last_char: " << s[i] << endl;
      }
    }
    
    if (last_repeat_seq.size > 2) {
      contiguous_repeats.push_back(last_repeat_seq);
      //cout << "adding contiguous seq: [" << last_repeat_seq.start << ", " << last_repeat_seq.size << ")\n";
    }
    
    // Let's break this up. We can try to merge the conditions later. First, assuming the string is the right size.
    if (s.size() >= 6 && s.size() <= 20) {
      // Each triplet that exists while a binary req is missing can be fixed in just one change.
      auto triplets = breakByReplacementOrAddition(contiguous_repeats);
      for (size_t i = 0; triplets > 0 && i < 3; ++i) {
        if (!reqs[i]) triplets--;
      }
      
      return !reqs[HAS_LOWER] + !reqs[HAS_UPPER] + !reqs[HAS_DIGIT] + triplets;  // This is probably going to be close to the return for all branches.
    } else if (s.size() < 6) {
      // Obviously, we need to change all triplets and so the same logic as above needs to happen,
      // though we could try not to double-count needing to add a char with needing to add a digit or upper.
      auto triplets = breakByReplacementOrAddition(contiguous_repeats);
      for (size_t i = 0; triplets > 0 && i < 3; ++i) {
        if (!reqs[i]) triplets--;
      }
      
      auto too_small = 6 - s.size();
      for (size_t i = 0; too_small && i < 3; ++i) {
        if (!reqs[i]) too_small--;
      }
      return !reqs[HAS_LOWER] + !reqs[HAS_UPPER] + !reqs[HAS_DIGIT] + triplets + too_small;
    } else {
      // s is too long, need to delete characters
      
      // Let's get smart!
      // Input: with MAX = 10, s = AAAAAABBBBBB (2 over)
      // Our algorithm will remove two A's and have this: AAAABBBBBB
      // That's two deletions + three edits to remove triplets making 5 edits total.
      
      // Instead, remove one of the A's and one of the B's: AAAAABBBBB
      // Now replace the middle A and B and you have solved it in 4: AA1AABB2BB
      // Now what's the algorithm!?
      // Especially considering that our current approach of deleting minimum
      // elements works best when this removes the need for futher edits. We can't
      // just try deleting from the largest sequences in all cases.
      
      // Idea: We can at any time estimate how many replcacements would still be needed after
      //       a deletion. In the above example, at the start it's four. After deleting two
      //       of the A's it's three. Similarly, after  deleting one of the A's, it's three.
      //       Deleting one of the B's instead shrinks it down to two so that solution is better.
      
      // Counter example: aaaaabbbb with two to delete
      // At the start, both sequences require only one replacement. Here, we should prioritize the smaller of the two.
      
      // Counter counter: aaaaaaaAAAAAA6666bbbbaaaaaa with 7 to remove
      //                  aaaaaaaAA____66__bb__aaa___ 
      // If we only remove one at a time, we suffer from the horizon effect. Removing from the first sequence of a's
      // would have reduced the number of replacements better, but the algorithm only know that removing one would
      // improve neither. We can try only deleting one at a time, but we should consider if deleting at most two
      // would lead to a better outcome. We don't need to think larger than two because it should just work out.
      
      size_t chars_to_remove = s.size() - 20;
      
      
      unsigned int deletions = 0;
      
      // Deleting from a repeat is always correct while we're too large.
      while (chars_to_remove && contiguous_repeats.size()) {
        // Find the sequence which would have the least number of replacements needed after a deletion.
        auto it = std::min_element(contiguous_repeats.begin(), contiguous_repeats.end(),
                            [&](const Seq& a, const Seq& b) {
                              size_t gain_from_deletion_a = a.size / 3 - (a.size - min(chars_to_remove, 2ul)) / 3;
                              size_t gain_from_deletion_b = b.size / 3 - (b.size - min(chars_to_remove, 2ul)) / 3;
                              return std::tuple(gain_from_deletion_a, b.size) > std::tuple(gain_from_deletion_b, a.size);
                            });
        size_t rm = 1;
        chars_to_remove -= rm;
        it->size -= rm;
        deletions += rm;

        if (it->size < 3) contiguous_repeats.erase(it);
      }
      
      // Now the contiguous repeats have shrunk in size and there are less chars to remove.
      // Some members of contiguous_repeats might be smaller than a triplet, but that should be okay.
      auto triplets = breakByReplacementOrAddition(contiguous_repeats);
      for (size_t i = 0; triplets > 0 && i < 3; ++i) {
        if (!reqs[i]) triplets--;
      }
      
      return !reqs[HAS_LOWER] + !reqs[HAS_UPPER] + !reqs[HAS_DIGIT] + triplets + deletions + chars_to_remove;
    }
  }
};