Beautiful Number Validator

Question

Problem

Adapted from this HackerRank problem.

A numeric string, \$s\$ is beautiful if it can be split into a sequence of two or more positive integers, \$a_1, a_2,...,a_n\$, satisfying the following conditions:

1. \$a_i - a_{a-1} = 1\$ for any \$1 \lt i\le n\$ (i.e., each element in the sequence is 1 more than the previous element).
2. No \$a_i\$ contains a leading zero. For example, we can split \$s = 10203\$ into the sequence {\$1, 02, 03\$}, but it is not beautiful because \$02\$ and \$03\$ have leading zeroes.
3. The contents of the sequence cannot be rearranged. For example, we can split \$s = 312\$ into the sequence {\$3, 1, 2\$}, but it is not beautiful because it breaks our first constraint (i.e., \$1 - 3 \ne 1\$).

Instead of printing YES or NO, I just wanted to return a boolean.

Description

The way I thought about implementing a solution was iterating through all the potential sequences that could be formed.

Because sequences are determined by the value of the first integer, by iterating through all the potential first integer values, you can generate all potential solutions.

For example, take the numeric string 123456. Let's say the first integer is 1. Then the next integer in the sequence would be 2 and so on. However, let's say the first integer is actually 12. Then the next integer in the sequence should then be 13. But it's actually 34. Thus, 12 cannot be the first integer in the sequence. Same if we decided that 123 was the first integer in the sequence.

If we exhaust all possibilities for what the first integer could be, then the numeric string cannot be beautiful.

Implementation Notes

In order to test all possible first integer values, we need to generate all prefixes for the input numeric string that are of length 1 to the length of the input string, rounded down.

For each prefix value, add it to a StringBuilder instance. Then, append the next integer value (so the integer after the prefix value, then the integer after, etc.) until the StringBuilder string length is greater than or equal to the input string or the StringBuilder string, up to that point, does not match the input string.

After exiting this loop, check to see if the StringBuilder string matches the input string. If so, then the string is indeed "beautiful".

If not, move on to the next potential prefix / first integer - if these have all been exhausted, then return false.

Implementation

public class BeautifulNumberValidator {
  public static boolean isValidBeautifulNumber(String s) {
    if (s.length() < 2) {
      return false;
    }

    for (int substringSize = 1; substringSize <= s.length() / 2; substringSize++) {
      long value = Long.parseLong(s.substring(0, substringSize));

      if (value == 0) {
        break;
      }

      StringBuilder sb = new StringBuilder();
      sb.append(value);

      while (sb.length() < s.length() && sb.toString().equals(s.substring(0, sb.length()))) {
        sb.append(++value);
      }

      if (sb.toString().equals(s)) {
        return true;
      }
    }

    return false;
  }
}

Answer 1

Remove redundant code

    if (s.length() < 2) {
      return false;
    }

This is unnecessary. If s.length() is less than two, then 1 <= s.length() / 2 will be false, as 1/2 is 0 in integer math. So it will drop through to the final return.

Say what you'll do

      if (value == 0) {
        break;
      }

You could write this more readably as

      if (value == 0) {
        return false;
      }

But it's not necessarily so that this would ever be called. It's also not clear that this is correct behavior. For example, this would break an octal or hexadecimal integer that is formatted with a leading zero.

Don't repeat work

     while (sb.length() < s.length() && sb.toString().equals(s.substring(0, sb.length()))) {
        sb.append(++value);
      }

This doesn't require a StringBuilder. Consider

      int i = 0;
      while (i < s.length()) {
        String number = String.valueOf(value);
        if (!s.substring(i, i + number.length()).equals(number)) {
          break;
        }
        i += number.length();
        value++;
      }

Instead of comparing two ever lengthening strings, this compares just the string representation of the current value.

Does this matter? You choose to parse into a long value. That only matters if the number is more than ten digits. Every single nine-digit value will fit into an int. This suggests that the beautiful number can be at least twenty digits long.

This doesn't quite fit in the logic of your original program, so I rewrote it as a helper method.

    public static boolean isValidBeautifulNumber(String s, long prefix) {
        for (int i = 0; i < s.length(); ) {
            String number = String.valueOf(prefix);
            if (!s.substring(i, i + number.length()).equals(number)) {
                return false;
            }

            i += number.length();
            prefix++;
        }

        return true;
    }

    public static boolean isValidBeautifulNumber(String s) {
        for (int substringSize = 1; substringSize <= s.length() / 2; substringSize++) {
            if (isValidBeautifulNumber(s, Long.parseLong(s.substring(0, substringSize)))) {
                return true;
            }
        }

        return false;
    }

This significantly simplifies the logic.

If each \$a_i\$ matches the original string, we make it through the loop and return true. If any fail to match, we return false.