class Solution {
 public:
  string minAbbreviation(string target, vector<string>& dictionary) {
    const int m = target.length();
    vector<int> masks;

    for (const auto& word : dictionary) {
      if (word.length() != m)
        continue;
      masks.push_back(getMask(target, word));
    }

    if (masks.empty())
      return to_string(m);

    vector<string> abbrs;

    const int maxCand = pow(2, m);
    // for all candidate representation of target
    for (int cand = 0; cand < maxCand; ++cand)
      // all masks have at lease one bit different from candidate
      if (all_of(begin(masks), end(masks),
                 [cand](int mask) { return cand & mask; }))
        abbrs.push_back(getAbbr(target, cand));

    string ans = target;

    for (const auto& abbr : abbrs)
      if (getAbbrLen(abbr) < getAbbrLen(ans))
        ans = abbr;

    return ans;
  }

 private:
  int getMask(const string& target, const string& word) {
    const int m = target.length();
    // mask[i] = 0 := target[i] == word[i]
    // mask[i] = 1 := target[i] != word[i]
    // e.g. target = "apple"
    //        word = "blade"
    //        mask =  11110
    int mask = 0;
    for (int i = 0; i < m; ++i)
      if (word[i] != target[i])
        mask |= 1 << m - 1 - i;
    return mask;
  }

  string getAbbr(const string& target, int cand) {
    const int m = target.length();
    string abbr;
    int replacedCount = 0;
    for (int i = 0; i < m; ++i)
      if (cand >> m - 1 - i & 1) {
        // cand[i] = 1, abbr should show the original character
        if (replacedCount)
          abbr += to_string(replacedCount);
        abbr += target[i];
        replacedCount = 0;
      } else {
        // cand[i] = 0, abbr can be replaced
        ++replacedCount;
      }
    if (replacedCount)
      abbr += to_string(replacedCount);
    return abbr;
  }

  int getAbbrLen(const string& abbr) {
    int abbrLen = 0;
    int i = 0;
    int j = 0;
    while (i < abbr.length()) {
      if (isalpha(abbr[j]))
        ++j;
      else
        while (j < abbr.length() && isdigit(abbr[j]))
          ++j;
      ++abbrLen;
      i = j;
    }
    return abbrLen;
  }
};

class Solution {
  public String minAbbreviation(String target, String[] dictionary) {
    final int m = target.length();
    List<Integer> masks = new ArrayList<>();

    for (final String word : dictionary) {
      if (word.length() != m)
        continue;
      masks.add(getMask(target, word));
    }

    if (masks.isEmpty())
      return String.valueOf(m);

    List<String> abbrs = new ArrayList<>();

    final int maxCand = (int) Math.pow(2, m);
    // for all candidate representation of target
    for (int i = 0; i < maxCand; ++i) {
      final int cand = i;
      // all masks have at lease one bit different from candidate
      if (masks.stream().allMatch(mask -> (cand & mask) > 0))
        abbrs.add(getAbbr(target, cand));
    }

    String ans = target;

    for (final String abbr : abbrs)
      if (getAbbrLen(abbr) < getAbbrLen(ans))
        ans = abbr;

    return ans;
  }

  private int getMask(final String target, final String word) {
    final int m = target.length();
    // mask[i] = 0 := target[i] == word[i]
    // mask[i] = 1 := target[i] != word[i]
    // e.g. target = "apple"
    //        word = "blade"
    //        mask =  11110
    int mask = 0;
    for (int i = 0; i < m; ++i)
      if (word.charAt(i) != target.charAt(i))
        mask |= 1 << m - 1 - i;
    return mask;
  }

  String getAbbr(final String target, int cand) {
    final int m = target.length();
    StringBuilder sb = new StringBuilder();
    int replacedCount = 0;
    for (int i = 0; i < m; ++i)
      if ((cand >> m - 1 - i & 1) == 1) {
        // cand[i] = 1, abbr should show the original character
        if (replacedCount > 0)
          sb.append(replacedCount);
        sb.append(target.charAt(i));
        replacedCount = 0;
      } else {
        // cand[i] = 0, abbr can be replaced
        ++replacedCount;
      }
    if (replacedCount > 0)
      sb.append(replacedCount);
    return sb.toString();
  }

  int getAbbrLen(final String abbr) {
    int abbrLen = 0;
    int i = 0;
    int j = 0;
    while (i < abbr.length()) {
      if (Character.isAlphabetic(abbr.charAt(j)))
        ++j;
      else
        while (j < abbr.length() && Character.isDigit(abbr.charAt(j)))
          ++j;
      ++abbrLen;
      i = j;
    }
    return abbrLen;
  }
}

class Solution:
  def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
    m = len(target)

    def getMask(word: str) -> int:
      # mask[i] = 0 := target[i] == word[i]
      # mask[i] = 1 := target[i] != word[i]
      # e.g. target = "apple"
      #        word = "blade"
      #        mask =  11110
      mask = 0
      for i, c in enumerate(word):
        if c != target[i]:
          mask |= 1 << m - 1 - i
      return mask

    masks = [getMask(word) for word in dictionary if len(word) == m]
    if not masks:
      return str(m)

    abbrs = []

    def getAbbr(cand: int) -> str:
      abbr = ''
      replacedCount = 0
      for i, c in enumerate(target):
        if cand >> m - 1 - i & 1:
          # cand[i] = 1, abbr should show the original character
          if replacedCount:
            abbr += str(replacedCount)
          abbr += c
          replacedCount = 0
        else:
          # cand[i] = 0, abbr can be replaced
          replacedCount += 1
      if replacedCount:
        abbr += str(replacedCount)
      return abbr

    # for all candidate representation of target
    for cand in range(2**m):
      # all masks have at lease one bit different from candidate
      if all(cand & mask for mask in masks):
        abbr = getAbbr(cand)
        abbrs.append(abbr)

    def getAbbrLen(abbr: str) -> int:
      abbrLen = 0
      i = 0
      j = 0
      while i < len(abbr):
        if abbr[j].isalpha():
          j += 1
        else:
          while j < len(abbr) and abbr[j].isdigit():
            j += 1
        abbrLen += 1
        i = j
      return abbrLen

    return min(abbrs, key=lambda x: getAbbrLen(x))