Redouble each occurrence of char recursively, and add n

Question

In following of this question, I would like to have a second review.

The exercise is to write a recursive method that takes a String and a char parameter and returns a String with each occurrence of the char doubled. Additionally, the number of doubling operations should be added at the end of the string. No "extern" variables outside the method are allowed to use. The String parameter can contain any valid char, including numbers.

It's not allowed to use other (recursive) helper methods. The method signature and parameters must not to be change.

My code is working correctly now (I hope), but how to replace the "pre-"calculated map from line 7 to 25 with a simple formula/term? Thanks in advance.

import java.util.HashMap;
public class Redouble {
 public static String redouble(final String s, final char c) {
 if (s.length() > 0) {
 if (s.charAt(0) == c) {
 HashMap<Integer, Integer> map = new HashMap<>();
 map.put(2, 1);
 for (int j = 1; j <= 4; j++) {
 int n0 = (int) Math.pow(10, j - 1);
 int n1 = (int) Math.pow(10, j);
 int i = n0;
 for (; i < n0 + j; i++) {
 int x = ((int) Math.log10(i) + i * 2 + 3 - j) / 2;
 if (!map.containsKey(x)) {
 map.put(x, j - 1);
 }
 }
 for (; i < n1; i++) {
 int x = ((int) Math.log10(i) + i * 2 + 3 - j) / 2;
 if (!map.containsKey(x)) {
 map.put(x, j);
 }
 }
 }
 //System.out.println("map = " + map);
 int len1 = s.length();
 String s1 = "" + c + c + redouble(s.substring(1), c);
 int len2 = s1.length();
 int lenDiff = len2 - len1;
 if (lenDiff > 0) {
 int x = map.get(lenDiff);
 //System.out.println(lenDiff + " " + x);
 int n = Integer.parseInt(s1.substring(s1.length() - x));
 return s1.substring(0, s1.length() - x) + (n + 1);
 }
 return s1;
 }
 return "" + s.charAt(0) + redouble(s.substring(1), c);
 }
 return "0";
 }
 public static void main(final String[] args) {
 // Some tests...
 String s = "0cac1c01";
 for (int i = 2; i <= 1010; i++) {
 s += "a";
 String s2 = redouble(s, 'a');
 System.out.println("Expected: " + i + ", actual: " + s2.substring(s2.length() - (int) Math.log10(i) - 1));
 if (!String.valueOf(i).equals(s2.substring(s2.length() - (int) Math.log10(i) - 1))) {
 System.out.println("ERROR");
 return;
 }
 }
 }
}

• Ralf Kleberhoff: Could you please copy the problem statement from the other question, so we don't have to switch between two different ones? And is it a requirement that you recursively call the "method that takes a String and a char" recursively? Or is it allowed to use recursion in a helper method with additional parameters, as that would allow for a much simpler solution.
• Tobias Grothe: Thanks, I have edited my question with additional details.

Answer 1

You can calculate the number of doublings instead of looking it up in a map. The code below is otherwise copied from @Roman's answer.

public static String redouble(final String s, final char c) {
 if (s.length() <= 0) {
 return "0";
 }
 if (s.charAt(0) != c) {
 return "" + s.charAt(0) + redouble(s.substring(1), c);
 }
 
 String original = s.substring(1);
 String doubled = redouble(original, c);
 // 1st estimate overestimates n because it includes its own string representation
 // 2nd estimate is correct or underestimates by one, as the length difference between
 // (n + n.toString().length()).toString() and n.toString() is 0 or 1 (prove it yourself)
 // 3rd estimate is definitely correct
 int n = doubled.length() - original.length();
 n -= ("" + n).length();
 if ((original + n).length() + n != doubled.length()) {
 n += 1;
 }
 return "" + c + c + doubled.substring(0, original.length() + n) + (n + 1);
}

The most complicated part is proving the assertion mentioned in the comment. The table illustrates what you have to prove for all n (the length difference is always 0 or 1):

 n len(n) n + len(n) len(n + len(n)) difference
 0 1 1 1 0
 1 1 2 1 0
 2 1 3 1 0
 3 1 4 1 0
 4 1 5 1 0
 ... 
 8 1 9 1 0
 9 1 10 2 1
 10 2 12 2 0
 11 2 13 2 0
 ...
 97 2 99 2 0
 98 2 100 3 1
 99 2 101 3 1
100 3 103 3 0
 ...

• Tobias Grothe: Thanks, solved. :) I have an edit suggestion for determine the int length...

Answer 2

Nested If-Statements

You can simplify the code and improve the readability as a result. It is achievable by using the Guard Pattern which in short can break off nested if-statements by inverting the condition:

public static String redouble(final String s, final char c) {
 if (s.length() <= 0) {
 return "0";
 }
 if (s.charAt(0) != c) {
 return "" + s.charAt(0) + redouble(s.substring(1), c);
 }
 
 HashMap<Integer, Integer> map = /* creating the map */;
 int len1 = s.length();
 String s1 = "" + c + c + redouble(s.substring(1), c);
 int len2 = s1.length();
 int lenDiff = len2 - len1;
 
 if (lenDiff <= 0) {
 return s1;
 }
 
 int x = map.get(lenDiff);
 int n = Integer.parseInt(s1.substring(s1.length() - x));
 return s1.substring(0, s1.length() - x) + (n + 1);
}

The code readability is improved by eliminating the nested if-statements. Now the code is understandable by reading from top to bottom without thinking about the nested conditions.

Good Names for Variables are important

Without really knowing you problem statement it is hard to understand the code because the naming of the variables is poor.

If you don't have a good name: Don't give it a name. Variables like len1 are useless. First it is an abbreviation for length which is really just three characters longer. Second when I see len1 I know, that there will be by minimum a len2. But as a reader I'm not interested in the enumeration; I'm interested in the difference (for example of the origin) of those lengths.

As I already said: Don't give them a name if the name is poor. s.length() gives me more context as len1:

int len1 = s.length();
String s1 = "" + c + c + redouble(s.substring(1), c);
int len2 = s1.length();
int lenDiff = len2 - len1;
if (lenDiff <= 0) {
 return s1;
}

The name s1 is somehow useless. Maybe doubled fits better? And len1 and len2 are only used to calculate the lenDiff, thus we can omit them. And the same for lenDiff. Additionally, original could be a better name for s1:

String doubled = "" + c + c + redouble(original.substring(1), c);
if (doubled.length() - original.length() <= 0) {
 return doubled;
}

Further Simplification

s.length() <= 0 can be expressed as s.isEmpty():

if (s.isEmpty()) {
 return "0";
}

How to simplify the Map?

There are two ways. The first one is by simplifying the creation of the map and the second one is by don't use a map at all.

Simplify the Creation of the Map

If I am right, the map will always look the same. This means you could write your map by hand without to calculate all the keys and values. But... the map has maaaany keys.

How does the map look like?

{2=1, /*...*/ , 12=1, 13=2, /*...*/, 103=2, 104=3, /*...*/, 1004=3, 1005=4, /*...*/, 10000=4}

And the map will always look like this, because there is no variable that will make it dynamic.

So actually you could simplify the creation of the map to:

HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < 13) {
 map.put(i, 1);
}
for(int i = 13; i < 104) {
 map.put(i, 2);
}
for(int i = 104; i < 1005) {
 map.put(i, 3);
}
for(int i = 1005; i < 10000) {
 map.put(i, 4);
}

Don't use a Map at all

The map is used in this statement: int x = map.get(lenDiff);.

Instead of storing 10000 values inside a map to only query one value you could calculate the value: int x = /* some math to caluclate the value of x */;.

I don't know enough about the problem and the math behind the precalculation of the map, to know how a calculation of x could look like.

• Tobias Grothe: Thanks. Can you tell something about creating or simplifying (avoiding) the map?
• Roman: Tobias, I edited my post to simplify and also to avoid the map. I hope it will help you.

Answer 3

You can simplify the calculation of the number of doubling operations using a mathematical formula instead of the pre-calculated map.

public class Redouble {
public static String redouble(final String s, final char c) {
 if (!s.isEmpty()) {
 if (s.charAt(0) == c) {
 int len1 = s.length();
 String s1 = "" + c + c + redouble(s.substring(1), c);
 int len2 = s1.length();
 int lenDiff = len2 - len1;
 if (lenDiff > 0) {
 // Extract the numeric part from the end of the string
 String numericPart = "";
 int index = s1.length() - 1;
 while (index >= 0 && Character.isDigit(s1.charAt(index))) {
 numericPart = s1.charAt(index) + numericPart;
 index--;
 }
 // Parse the numeric part as an integer
 int x = Integer.parseInt(numericPart);
 return s1.substring(0, s1.length() - numericPart.length()) + (x + 1);
 }
 return s1;
 }
 return "" + s.charAt(0) + redouble(s.substring(1), c);
 }
 return "0";
}
public static void main(final String[] args) {
 // Some tests...
 String s = "0cac1c01";
 for (int i = 2; i <= 1010; i++) {
 s += "a";
 String s2 = redouble(s, 'a');
 System.out.println("Expected: " + i + ", actual: " + s2.substring(s2.length() - (int) Math.log10(i) - 1));
 if (!String.valueOf(i).equals(s2.substring(s2.length() - (int) Math.log10(i) - 1))) {
 System.out.println("ERROR");
 return;
 }
 }
 }
}

Hope this helps

• Rainer P.: I think this will fail if the original string (before adding the number) ends with a digit. Your code will interpret that digit as part of the trailing number, which it isn't.