#902. 最大为 N 的数字组合

const remainingLength = target.length - position - 1;
result += digitCount ** remainingLength;

/**
 * 统计由 digits 中的数字重复组成，并且不大于 n 的正整数个数。
 *
 * 计数分为两部分：
 * 1. 位数少于 n 的数字，它们一定小于 n，可以直接用乘法原理计算。
 * 2. 位数等于 n 的数字，需要从高位到低位逐位和 n 比较。
 *
 * @param {string[]} digits 按升序排列且互不相同的数字字符，题目保证不包含 "0"
 * @param {number} n 上界
 * @return {number} 满足条件的正整数个数
 */
var atMostNGivenDigitSet = function (digits, n) {
  // 转为字符串，方便按下标从最高位到最低位访问 n 的每一位。
  const target = String(n);

  // 每一个数位可选择的数字数量。
  const digitCount = digits.length;

  // 累加所有合法数字的数量。
  let result = 0;

  /*
   * 第一部分：统计位数少于 n 的数字。
   *
   * 例如 digits 有 4 个数字、n 是三位数：
   * - 一位数有 4¹ 个；
   * - 两位数有 4² 个。
   *
   * digits 不包含 "0"，因此首位不需要排除前导零，每一位都有
   * digitCount 种选择。
   */
  for (let length = 1; length < target.length; length++) {
    result += digitCount ** length;
  }

  /*
   * 第二部分：统计与 n 位数相同的合法数字。
   *
   * 循环到 position 时，隐含条件是 position 之前的所有位都与 n 相等。
   * 因此只需要比较当前可选数字 digit 和 n 的当前位 target[position]。
   */
  for (let position = 0; position < target.length; position++) {
    // 记录当前位能否选择与 n 相同的数字，从而继续比较下一位。
    let hasEqualDigit = false;

    // digits 已按升序排列，可以从小到大检查当前位的所有选择。
    for (const digit of digits) {
      if (digit < target[position]) {
        /*
         * 当前位一旦比 n 的当前位小，整个数字就已经确定小于 n。
         * 后续每一位都可以从 digits 中任意选择，无须继续逐位比较。
         *
         * remainingLength 是当前位之后还剩多少位；
         * 对于当前这个较小的 digit，可以产生 digitCount^remainingLength
         * 个合法数字。
         */
        const remainingLength = target.length - position - 1;
        result += digitCount ** remainingLength;
      } else if (digit === target[position]) {
        /*
         * 当前位相等时，前缀仍然与 n 相同。
         * 这里只做标记，外层循环随后会继续比较下一位。
         */
        hasEqualDigit = true;
      } else {
        /*
         * 当前 digit 已经大于 n 的当前位。
         * 因为 digits 升序排列，后面的数字只会更大，都不可能合法。
         */
        break;
      }
    }

    /*
     * 如果当前位没有可选数字等于 n 的当前位，相等前缀无法延续。
     * 小于当前位的情况已在内层循环中全部计数，大于当前位的情况不合法，
     * 所以此时答案已经完整，可以提前返回。
     */
    if (!hasEqualDigit) {
      return result;
    }
  }

  /*
   * 能走完整个外层循环，说明 n 的每一位都存在于 digits 中，
   * 即 n 本身也能由 digits 组成。前面的 result 只统计了小于 n 的数字，
   * 因此最后加 1，把 n 自身计入。
   */
  return result + 1;
};

/**
 * 使用 digits 中的数字重复构造一个不大于 n 的最大正整数。
 *
 * @param {string[]} digits 非空、升序且互不相同的数字字符，不包含 "0"
 * @param {number} n 正整数上界
 * @return {number|null} 能构造出的最大数字；不存在合法正整数时返回 null
 */
function largestAtMostN(digits, n) {
  const target = String(n);
  const maxDigit = digits[digits.length - 1];

  /*
   * 第一部分：先保存“位数少于 n”的最大合法数字，作为初始候选。
   *
   * digits 不包含 "0"，不会出现前导零，因此位数少于 n 的正整数
   * 一定小于 n。在这些数字中，位数越多，数字越大，所以只需要考虑
   * target.length - 1 位，不必像原题计数那样枚举所有更短的长度。
   *
   * 数字可以重复使用，要让这个长度的数字最大，每一位都选 maxDigit。
   * maxDigit.repeat(target.length - 1) 生成对应字符串，再用 Number
   * 转成数字。例如 n = 365、maxDigit = "7"，初始候选就是 77。
   * 如果后面无法构造与 n 等长的合法数字，就返回这个较短的候选。
   *
   * 如果 n 只有一位，就不存在位数更少的正整数，因此先保存 null，
   * 表示尚未找到合法答案，而不是返回 0（题目要求正整数）。
   * 后续若找到合法的一位数，仍会更新候选或在完整匹配时返回 n；
   * 只有始终没有合法答案时才返回 null，例如 digits = ["5"]、n = 3。
   */
  let result = target.length > 1
    ? Number(maxDigit.repeat(target.length - 1))
    : null;

  // 第二部分：沿用原题结构，逐位匹配 n。
  // 进入 position 时，此前的前缀始终与 n 相等。
  for (let position = 0; position < target.length; position++) {
    let hasEqualDigit = false;

    for (const digit of digits) {
      if (digit < target[position]) {
        /*
         * 此前的前缀与 n 完全相同，当前 digit 又小于 n 的对应位，
         * 因此无论后面的位怎么选，组成的等长数字都一定小于 n。
         *
         * 原题在这里累加后续位置的组合数；变式只需要这个分支中
         * 最大的数字，所以后面的每一位都选择 maxDigit。
         */

        // 保留当前位之前的相等前缀，不包含当前位。
        // 能走到这里，说明前缀中的每个数字都已经在 digits 中匹配成功。
        const prefix = target.slice(0, position);

        // 当前位之后还剩多少位：总位数减去前缀位数，再减去当前这一位。
        const remainingLength = target.length - position - 1;

        // 后缀全部填最大数字；如果当前已是最后一位，后缀就是空字符串。
        const suffix = maxDigit.repeat(remainingLength);

        /*
         * 拼接“相等前缀 + 当前较小数字 + 最大后缀”，保存为候选答案。
         * 例如 n = 365、position = 1、digit = "5"、maxDigit = "7"：
         * prefix = "3"，suffix = "7"，得到候选 357。
         *
         * 可以直接覆盖 result：同一位置的 digit 按升序遍历，候选
         * 越来越大；更靠后的位置才变小，则比之前更早变小的候选大；
         * 等长候选也一定大于初始化时保存的较短数字。
         *
         * 这里只保存候选，不能立即返回：后面可能还有更大的 digit，
         * 或者可以选择相等数字并继续匹配，从而找到更大的合法答案。
         * 如果后续匹配失败，就能直接返回保存的候选，无须向前回退。
         */
        result = Number(prefix + digit + suffix);
      } else if (digit === target[position]) {
        // 前缀仍然相等，继续比较下一位。
        hasEqualDigit = true;
      } else {
        // digits 升序排列，后面的数字也不合法。
        break;
      }
    }

    // 相等前缀无法继续，返回之前保存的最大候选。
    if (!hasEqualDigit) {
      return result;
    }
  }

  // 每一位都在 digits 中，n 本身就是答案。
  return n;
}