How can I efficiently manipulate digits in a string without using RegEx in Java?

Question

I am reading a book with different quizzes about coding interviews.

Please implement a function that increments a string based on the rules below:

1. It should take the string of unknown length and increment the numberic ending of that string by 1.
2. If numberic ending is overflown it must be reset.
3. Don't use regular expressions

Examples of correct functionality are the following:

assertEquals("000003", increment("000002"));
assertEquals("000000", increment("999999"));
assertEquals("GL-322", increment("GL-321"));
assertEquals("GL-000", increment("GL-999"));
assertEquals("DRI000EDERS1RE", increment("DRI000EDERS0RE"));
assertEquals("DRI000EDERS0RE00000", increment("DRI000EDERS0RE99999"));

Here is my solution, I am sure it could be vastly more efficient / succinct:

public class Increment {
 static String padLeftZeros(String inputString, int length) {
 if (inputString.length() >= length) {
 return inputString;
 }
 StringBuilder sb = new StringBuilder();
 while (sb.length() < length - inputString.length()) {
 sb.append('0');
 }
 sb.append(inputString);
 return sb.toString();
 }
 static String increment(String referenceNumber) {
 // Finding the last digit index in referenceNumber
 int indexLastDigit = -1;
 for (int i = 0; i < referenceNumber.length(); i++){
 try {
 Integer.parseInt(String.valueOf(referenceNumber.charAt(i)));
 indexLastDigit = i;
 } catch (NumberFormatException nfe) {
 }
 }
 // Finding the first digit index of the last digit group in referenceNumber
 int indexFirstDigit = -1;
 for (int i = indexLastDigit; i >= 0; i--){
 try {
 Integer.parseInt(String.valueOf(referenceNumber.charAt(i)));
 indexFirstDigit = i;
 } catch (NumberFormatException nfe) {
 break;
 }
 }
 // Checking if numberToIncrement needs reset or not
 String numberToIncrement = referenceNumber.substring(indexFirstDigit, indexLastDigit + 1);
 boolean isReset = true;
 for (int i = 0; i < numberToIncrement.length(); i++){
 if (numberToIncrement.charAt(i) != '9') {
 isReset = false;
 }
 }
 // Incrementing or resetting number
 StringBuilder incrementedNumberSB = new StringBuilder();
 int incrementedNumberInt;
 if (isReset) {
 for (int i = 0; i < numberToIncrement.length(); i++){
 incrementedNumberSB.append("0");
 }
 } else {
 incrementedNumberInt = Integer.parseInt(numberToIncrement) + 1;
 incrementedNumberSB.append(incrementedNumberInt);
 }
 // Creating result string according to referenceNumber structure
 String incrementedNumberString = padLeftZeros(incrementedNumberSB.toString(), numberToIncrement.length());
 String prefix = referenceNumber.substring(0, indexFirstDigit);
 String suffix = referenceNumber.substring(indexLastDigit + 1, referenceNumber.length());
 String result = "";
 if (prefix.length() > 0) {
 result += prefix;
 }
 result += incrementedNumberString;
 if (suffix.length() > 0) {
 result += suffix;
 }
 return result;
 }
}

• Mast: assertEquals("DRI000EDERS1RE", increment("DRI000EDERS0RE")); Why? How should the program determine the correct result here? I think we're missing an important part of the challenge here. Are all numbers in base 10 and thus all non 0-9 characters irrelevant when incrementing? assertEquals("DRI000EDERS0RE00000", increment("DRI000EDERS0RE99999")); The incremented value doesn't roll over to the 0 in SORE?
• Carl Witthoft: Just pointing out that this isn't a 'in Java' question, as the answer will be almost identical in any language with similar syntax

Answer 1

TL;DR

private String increment(String input){
 char[] chars = input.toCharArray();
 boolean stopLoop = false;
 for(int i = chars.length - 1; i >= 0; i--){
 char character = chars[i];
 switch (character) {
 case '0', '1', '2', '3', '4', '5', '6', '7', '8' -> {
 chars[i] = (char) (character + 1);
 stopLoop = true;
 }
 case '9' -> chars[i] = '0';
 default -> {
 if(i + 1 < chars.length && chars[i + 1] == '0')
 stopLoop = true;
 }
 }
 if(stopLoop)
 break;
 }
 return new String(chars);
}

The quizzes of the coding interviews have some goals:

• To check if the knowledge that the candidate claims is true.
• To filter candidates when you have too many applications.
• To know if you think beyond the obvious solution.
• To know how deep you know about a language, or a version of it.
• To check if you have some knowledge of data structures, algorithms and time / space complexity of algorigthms.

Here the obvious solution is to work with Strings. Knowing that String in Java are immutable, you have to do all the stuff splitting and concatenating Strings. My proposal is to convert the String into a char array, work with it, and convert it back to an array.

The cost in time of reading and writting into an array is constant, while making all the work with strings has a higher time cost. In an interview is not so important, but for a backend position it is.

Is the char array the best thing ever? It is not, specially in this example. The good of it, is that you can use it like an integer of one byte space in memory. The bad, is because that behaviour, the editor wont tell you that you are writting 0 instead of '0'. 0 is the value of the NUL Ascii character. The Ascii value of '0' is 48. Well, this problem is designed to know if you write too error prone code.

When you have the char array, you traverse it backwards. To traverse backwards is more error prone than to traverse forwards (IndexOutOfBoundExceptions). So, it is another way to check how many errors do you write without the help of your editor, or without compiling several times.

Because you can use char as a value, it is perfect to use it into a switch statement. The first nine cases (from '0' to '8' character) share the same behaviour and code: Increment to next character and end the edition of the characters.

The case of character '9' requires to replace this character with '0' and check the previous character in the array.

The default case is the trickiest. It ignores the characters that aren't numbers if they appear before the characters that are numbers (remember, it is backwards traversing). When one number appears there are two options: the first option is one of the first nine cases, the other option is the case of a '9' converted into a '0'. So, if you find a non number character followed of a '0' the algorithm finishes.

The last step is to convert the char array back into a String, what you can do easily calling one of the String constructors.

You won't face this kind of problem in real life. You will use regular expresions. It is just to check you knowledge, in this case about Java. If you find a problem which solution is too complicate, try a less obvious one.

I hope it helped you.

• Pitto: What will happen if you have 000091 ? Expected result is 000092.
• Eric Duminil: @Pitto: It seems to work too, thanks to stopLoop.
• No More Hello World: @Pitto: assertEquals("000092", increment("000091")) is the same case as assertEquals("000003", increment("000002")), it correspond to the first nine cases of the switch statement. In any case, just write all possible combinations you doubt about as assertions or test cases and check the code. It is a fast way to check the possible options.
• Pitto: I don't have JDK 14 on my machine, can you please confirm that you pass all tests you can find in the question? Thanks @NoMoreHelloWorld
• No More Hello World: @Pitto: I confirm that the code pass all the test. Anyway, if you have Java 8, you only have to change the sintaxis of the switch statement.

Answer 2

Because this is an interview question, the most important part is the questions you ask. The questions show that you understand that requirements are seldom complete and know what kind of limitations affect the implementation of the algorithm. The ones that need to be asked here are:

1. How long are the input strings of typical input?
2. How long are the numeric values in the typical input?
3. Is the algorithm supposed to work efficiently on all possible scenarios or are shortcuts allowed to make the code more maintainable?
4. Bonus question: should the algorithm work with floating point numbers too?

Judging by the examples in the tests I have made assumptions that the intended usage works on relatively short strings and that makes this problem much easier than it seems at first. The requirement "reset to 0 when overflow" is the key to simplifying the solution.

• Loop in reverse order starting from last digit in the string. This requires that the whole string is in memory and will not work for infinitely long input (see question 1). But seeing as you've also loaded the string to memory, it won't be any worse.
• Add one to the first digit you find.
• If it overflows to 10 you set carry to true and set the digit to 0.
• Repeat adding one to the next digit as long as carry is true or a character is found.

Just like you would add one to a large number in first grade math. :)

Edit: One simplification that may or may not be a smart thing to do in an interview is to start the algorithm by having carry = true. That way you implicitely add one to the first digit without needing special checks. But this needs to be commented clearly in the code regardless of it being production or interview code. It might be a good way of showing that you recognize structures that may not be immediately clear to the reader and know how to document them in code.

And most importantly, this was a trick question that tells nothing about you as a programmer. If someone asks you this in an interview, it is a sign that they don't really know how to interview programmers. I would not have been able to whip out this solution in a stressful environment of a job interview. And I've been working 25 years as a senior developer/architect... Scenarios like this never occur at work. We have enough time to evaluate ideas, discuss them with other people, rewrite if we figure a better solution. The stressed out crap we write in an interview never represents what we are capable of at actual work.

• Carl Witthoft: +10 for the summary comment. Any interviewer who looks at the "what" rather than the "how" that you produce is a fool.
• Acccumulation: I don't think that having a variable to store carry is even necessary. If carry is false, you just exit out of the loop. You could also implement this as recursion rather than looping: increment last character, if that results in an overflow, call the function on the string up to the last character. Recursion takes more memory since there's a function stack, but conceptually it has advantages.
• Eric: @Acccumulation Unless you're in a language that converts recursion to a loop for you, recursion puts you at risk of stack overflows for long strings
• Bobby: I disagree with your last paragraph. It tells me enough about a person in an interview, that is, if it is not a whiteboard exercise. Given enough time, an IDE and a browser, and discussion before and afterwards, it tells me a lot about how a programmer approaches and solves problems. Combined with discussing the solution together, I think it is fine as an interview question if done right. Of course, it should not be the only thing during the interview.
• Bobby: Also regarding your last paragraph, I don't see any need to insult anybody about such an out of context question "they don't really know how to do an interview".

Answer 3

static String padLeftZeros(String inputString, int length) {

Having no modifier specified means that it is package-private. Personally, I like to pretend that package-private does not exist, as it easily leads to "hidden" coupling between classes, and makes it harder for extending classes to actually utilize the classes. On top of that, you can circumvent the restrictions by simply being in the same package, another thing that smells.

In this case, you most likely want private.

---

StringBuilder sb = new StringBuilder();
int incrementedNumberInt;

Your variable names are good, with a few minor exceptions, like these. The first one should be something like paddingZeros, and the second one should not have that Int postfix.

---

static String padLeftZeros(String inputString, int length) {

Consider whether a non-static utility would be better suited. But I guess in this exercise it doesn't really matter.

---

 if (inputString.length() >= length) {
 return inputString;
 }
 StringBuilder sb = new StringBuilder();
 while (sb.length() < length - inputString.length()) {
 sb.append('0');
 }
 sb.append(inputString);
 return sb.toString();

Java 11 introduced String.repeat(int) which would simplify your code:

 if (inputString.length() >= length) {
 return inputString;
 }
 
 String paddingZeros = "0".repeat(length - inputString.length());
 
 return padding + inputString;

---

 // Finding the last digit index in referenceNumber
 int indexLastDigit = -1;
 for (int i = 0; i < referenceNumber.length(); i++){
 try {
 Integer.parseInt(String.valueOf(referenceNumber.charAt(i)));
 indexLastDigit = i;
 } catch (NumberFormatException nfe) {
 }
 }

A better option would be Character.isDigit(int), and looping backwards through the string. You could extract that code into an extra function for better readability:

private static int lastIndexOfDigit(String input) {
 for (int index = input.length - 1; index >= 0; index--) {
 if (Character.isDigit(input.codePointAt(index)) {
 return index;
 }
 }
 
 return -1;
}

---

 // Finding the first digit index of the last digit group in referenceNumber
 int indexFirstDigit = -1;
 for (int i = indexLastDigit; i >= 0; i--){
 try {
 Integer.parseInt(String.valueOf(referenceNumber.charAt(i)));
 indexFirstDigit = i;
 } catch (NumberFormatException nfe) {
 break;
 }
 }

Same here, a loop with Character.isDigit would be better.

---

 // Checking if numberToIncrement needs reset or not
 String numberToIncrement = referenceNumber.substring(indexFirstDigit, indexLastDigit + 1);
 boolean isReset = true;
 for (int i = 0; i < numberToIncrement.length(); i++){
 if (numberToIncrement.charAt(i) != '9') {
 isReset = false;
 }
 }

This would also do well in its own function. Also, isReset is an odd name, it should either be requiresReset, willReset, isMaximum or willOverflow.

Also also, I'm very sure there is an easier way to do this mathematically, but I can't think of that one right now.

---

 // Incrementing or resetting number
 StringBuilder incrementedNumberSB = new StringBuilder();
 int incrementedNumberInt;
 if (isReset) {
 for (int i = 0; i < numberToIncrement.length(); i++){
 incrementedNumberSB.append("0");
 }
 } else {
 incrementedNumberInt = Integer.parseInt(numberToIncrement) + 1;
 incrementedNumberSB.append(incrementedNumberInt);
 }

This assumes that the number will fit into an int. Maybe BigInteger would be safer thing to use here.

And again, String.repeat would come in handy here.

---

String suffix = referenceNumber.substring(indexLastDigit + 1, referenceNumber.length());

You can omit the second parameter.

---

 if (prefix.length() > 0) {
 result += prefix;
 }
 result += incrementedNumberString;
 if (suffix.length() > 0) {
 result += suffix;
 }
 return result;

I'd really not care whether they have length or not, just concatenate the three strings. If you want to check that, I'd check it before creating a new substring from it.

Answer 4

Extract some of the logic to methods.

As suggested by @bobby, the code in the Increment#increment method can be extracted in more than one method.

I suggest that you extract the logic into multiples new methods; this will make the code shorter, easier to read and make the code more testable in any test framework (you will be able to test each new method with unit tests).

1. To get the last index of the digit.

private static int findIndexLastDigit(String referenceNumber) {
 int indexLastDigit = -1;
 for (int i = 0; i < referenceNumber.length(); i++) {
 try {
 Integer.parseInt(String.valueOf(referenceNumber.charAt(i)));
 indexLastDigit = i;
 } catch (NumberFormatException nfe) {
 }
 }
 return indexLastDigit;
}

2. To get the first index of the digit.

private static int findIndexFirstDigit(String referenceNumber, int indexLastDigit) {
 int indexFirstDigit = -1;
 for (int i = indexLastDigit; i >= 0; i--) {
 try {
 Integer.parseInt(String.valueOf(referenceNumber.charAt(i)));
 indexFirstDigit = i;
 } catch (NumberFormatException nfe) {
 break;
 }
 }
 return indexFirstDigit;
}

3. To find the number to increase.

private static String findNumberToIncrement(String referenceNumber, int indexLastDigit, int indexFirstDigit) {
 return referenceNumber.substring(indexFirstDigit, indexLastDigit + 1);
}

4. To check if we need to reset the number we increment.

private static boolean needToResetNumberToIncrement(String numberToIncrement) {
 boolean isReset = true;
 for (int i = 0; i < numberToIncrement.length(); i++) {
 if (numberToIncrement.charAt(i) != '9') {
 isReset = false;
 }
 }
 return isReset;
}

The loop can be optimized, since we know that the reset is not needed, we can break the loop early to prevent the iteration.

for (int i = 0; i < numberToIncrement.length(); i++) {
 if (numberToIncrement.charAt(i) != '9') {
 return false;
 }
}
return true;

5. To handle the reset of the number, if needed.

private static String handleNumberIncrementOrReset(String numberToIncrement) {
 boolean isReset = needToResetNumberToIncrement(numberToIncrement);
 // Incrementing or resetting number
 StringBuilder incrementedNumberSB = new StringBuilder();
 int incrementedNumberInt;
 if (isReset) {
 incrementedNumberSB.append("0".repeat(numberToIncrement.length())); // As suggested by @bobby, you can use the `java.lang.String.repeat`
 } else {
 incrementedNumberInt = Integer.parseInt(numberToIncrement) + 1;
 incrementedNumberSB.append(incrementedNumberInt);
 }
 return incrementedNumberSB.toString();
}

6. A method that handles the replacement of the number, if needed.

private static String replaceNumber(String referenceNumber, int indexLastDigit, int indexFirstDigit, String numberToIncrement, String incrementedNumberSB) {
 String incrementedNumberString = padLeftZeros(incrementedNumberSB, numberToIncrement.length());
 String prefix = referenceNumber.substring(0, indexFirstDigit);
 String suffix = referenceNumber.substring(indexLastDigit + 1, referenceNumber.length());
 String result = "";
 if (prefix.length() > 0) {
 result += prefix;
 }
 result += incrementedNumberString;
 if (suffix.length() > 0) {
 result += suffix;
 }
 return result;
}

This will make the Increment#increment shorter.

static String increment(String referenceNumber) {
 // Finding the last digit index in referenceNumber
 int indexLastDigit = findIndexLastDigit(referenceNumber);
 // Finding the first digit index of the last digit group in referenceNumber
 int indexFirstDigit = findIndexFirstDigit(referenceNumber, indexLastDigit);
 // Checking if numberToIncrement needs reset or not
 String numberToIncrement = findNumberToIncrement(referenceNumber, indexLastDigit, indexFirstDigit);
 String incrementedNumberSB = handleNumberIncrementOrReset(numberToIncrement);
 // Creating result string according to referenceNumber structure
 return replaceNumber(referenceNumber, indexLastDigit, indexFirstDigit, numberToIncrement, incrementedNumberSB);
}