Issue
Geek wants to send an encrypted message in the form of string S to his friend Keeg along with instructions on how to decipher the message. To decipher the message, his friend needs to iterate over the message string from left to right, if he finds a *, he must remove it and add all the letters read so far to the string. He must keep on doing this till he gets rid of all the *.
Can you help Geek encrypt his message string S?
Note: If the string can be encrypted in multiple ways, find the smallest encrypted string.
Example 1:
Input: S = "ababcababcd"
Output: ab*c*d
Explanation: We can encrypt the string
in following way : "ababcababcd" -> "ababc*d" -> "ab*c*d"
Example 2:
Input: S = "zzzzzzz"
Output: z*z*z
Explanation: The string can be encrypted
in 2 ways: "z*z*z" and "z**zzz". Out of
the two "z*z*z" is smaller in length.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints: 1 ≤ |S| ≤ 105
Answer:
public String compress(String s) {
if(s.length()==1) return s;
if(s.length()%2==0){
if(s.substring(0,s.length()/2).equals(s.substring(s.length()/2,s.length()))) {
return s.substring(0,s.length()/2)+"*";
}
}
String left=compress(s.substring(0,s.length()-1))+s.charAt(s.length()-1);
return left;
}
I'm not getting proper solution from this code,but in some cases,it shows this java.lang.OutOfMemoryError in the main method.
Solution
Please make it sure that the max length of string s possible is 10^5 and not 105 (I referred the question at GFG). Since the length of string is so large that if the above method is used, then there might be some cases where the JVM might not be able to assign memory to the recursive calls of the method.
Hence it displays the outofmemory error as usual.
Answered By - HARSH KUMAR CHOUDHARY
Answer Checked By - David Marino (JavaFixing Volunteer)
