1. Reverse only the numbers in a string.
Given a string such as 72abd18b, reverse only the digits while leaving the letters in place.
I would use two pointers, one from the left and one from the right. I convert the string to a character array so I can swap characters. Each pointer skips non-digit characters until it reaches a digit. When both pointers are on digits, I swap them and move inward. This reverses only the digits while every letter stays in its original position. The time complexity is O(n), and the auxiliary space is O(n) because Java creates a character array.
See the Code while reading this explanation.
The input is a string that contains letters and digits. We only reverse the digits. The letters must stay exactly where they are. For example, the input is 72abd18b. Its digits from left to right are 7, 2, 1, 8. Reversing those digits gives 8, 1, 2, 7. Putting them back into the same digit positions gives 81abd27b. A two-pointer method fits well because one pointer can find the next digit from the left while the other finds the next digit from the right.
- Should only digit characters be reversed while all non-digit characters stay in their original positions?
- Is returning a new string acceptable, since Java String objects are immutable?
The input is 72abd18b. The required output is 81abd27b. The letters a, b, d, and b stay at indices 2, 3, 4, and
- Only the characters at digit positions change. The original digit order is 7, 2, 1,
- The reversed digit order is 8, 1, 2, 7.
I use two pointers and a char array. The left pointer searches from the beginning for the next digit. The right pointer searches from the end for the next digit. The char array lets me swap characters because Java String objects cannot be modified. The invariant is that letters never move, and digit positions outside the current pointer range already contain their final reversed digit values.
I convert the input into the character array [7, 2, a, b, d, 1, 8, b]. I set left = 0 and right = 7. Traversal starts at both ends of the array.
At the first step, left is 0 and points to 7. Right starts at 7, which contains b, so right moves to 6, which contains 8. Both pointers are now on digits. I swap indices 0 and 6. The state changes from 72abd18b to 82abd17b. Then left becomes 1 and right becomes 5.
At the second step, left is 1 and points to 2. Right is 5 and points to 1. Both pointers are on digits, so I swap indices 1 and 5. The state changes from 82abd17b to 81abd27b. Then left becomes 2 and right becomes 4.
Next, left sees a at index 2 and moves to index 3. It sees b at index 3 and moves to index 4. Now left = 4 and right = 4. The condition left < right is false, so the loop stops. The d at index 4 is never moved. The final result is 81abd27b.
The left pointer finds the next digit that still needs a value from the right side. The right pointer finds the matching digit from the opposite side. Swapping those two digits puts the correct reversed values at both ends of the active range. Non-digit characters are only skipped, so their positions never change. Repeating this until the pointers meet reverses all digit positions correctly.
The method converts the input String to char[]. It initializes left at 0 and right at the last index. Inside the main loop, the left inner loop skips non-digits from the front. The right inner loop skips non-digits from the back. When both pointers are on digits and left < right, the code swaps chars[left] and chars[right], then increments left and decrements right. When the pointers meet or cross, the method returns a new String built from the modified array.
The time complexity is O(n). Each pointer moves only inward, so each character is examined at most a constant number of times. The auxiliary space is O(n) because toCharArray() creates a character array whose size grows with the input. Relevant edge cases are a string with no digits, a string containing only digits, a string with one digit, and adjacent or repeated digits.
The key idea is to change only digit positions. A left pointer searches for the next digit from the front, and a right pointer searches for the next digit from the back. Non-digit characters are skipped. When both pointers are on digits, those two digits are swapped and both pointers move inward. The central invariant is that letters remain at their original indices, while digit positions outside the current [left, right] range already contain their final reversed values. This lets the algorithm reverse the digit sequence directly without storing a separate list of digits.
public class Main {
public static String reverseDigits(String s) {
// Convert the immutable String to a mutable character array
// so digit positions can be swapped.
char[] chars = s.toCharArray();
// Start one pointer at each end of the array.
int left = 0;
int right = chars.length - 1;
// Continue while there are still two different positions to compare.
while (left < right) {
// Skip non-digit characters from the left.
// They must remain in their current positions.
while (left < right && !Character.isDigit(chars[left])) {
left++;
}
// Skip non-digit characters from the right.
// They also remain in their current positions.
while (left < right && !Character.isDigit(chars[right])) {
right--;
}
// When both pointers are on digits, swap those two digits.
if (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
// These two digit positions are now correct, so move inward.
left++;
right--;
}
}
// Build the final String from the modified character array.
return new String(chars);
}
public static void main(String[] args) {
// Run the exact example used in the diagram.
String input = "72abd18b";
String result = reverseDigits(input);
// Expected output: 81abd27b
System.out.println(result);
}
}Let n be the number of characters in the string. The time complexity is O(n). The left pointer only moves right, and the right pointer only moves left, so the input is processed at most a constant number of times per character. The auxiliary space is O(n). Java creates a char array of size n so the characters can be swapped. The returned String is then built from that final character array.
This two-pointer pattern is useful when selected elements must be rearranged while other positions stay fixed. Similar logic can reverse only digits, only letters, only vowels, or other characters that match a condition without moving the remaining characters.
This problem tests whether you can recognize a two-pointer pattern and apply it only to selected characters. The interviewer can evaluate whether you move each pointer for the correct reason, keep letters fixed, maintain a useful invariant, and stop when the pointers meet. It also checks basic Java string handling, Character.isDigit(...), swapping logic, edge-case thinking, and whether you can explain O(n) time and O(n) auxiliary space correctly.
One common mistake is swapping before both pointers are on digits. That can move a letter and break the requirement. Another mistake is moving the wrong pointer when a non-digit character is found. A candidate may also forget to move both pointers inward after a successful swap, which can process the same digit again. Another mistake is reversing the whole string instead of only the digit positions. Finally, do not claim O(1) auxiliary space for this Java implementation because the char array grows with the input size.
State the invariant before coding: letters never move, and digit positions outside the current pointer range are already correct. Then trace the exact two swaps, 7 with 8 and 2 with 1. This makes the pointer movement and stopping condition easy to explain.
