Reversing string containing [] which carry special meaning.

[Kashif Ahmed Khan]

Hi,

I have a question. I have to reverse a string. The requirements are as follows.

1. From standard String.java class, only length() and charAt(int index) can be used.
2. Other Standard Java classes can be used.
3. If a string contains '[' and ']' then the string inside that shouldn't be reversed. However, if there are multiple instances then the pair of '[' ']' coming inside another '[' ']' will be reversed.
4. It should be thread safe and if there are not matching pairs of '[' ']' then some exception should be thrown.
5. The resulting reversed string should remove '[' and ']'.

e.g. If we have the following string.
Input = "This string [will not be reversed but [this inside here will be reversed] and this will not be reversed ] however, this part is reversed".
Output = "desrever si trap, revewoh will not be reversed but desrever eb lliw ereh rdisne sith will not be reversed gnirts sith".

How can we solve this. All ideas will be appreciated.

Regards

[Jeff Verdegan]

Step 1: Forget that computers exist.

You need to figure out how to solve this "manually". And more importantly, you need to express that solution in very clear, precise, simple steps. Do that before you even think about writing a line of Java code.

Write down your solution in whatever combination of English/your native language/pseudocode is easiest for you. If you do this part correctly, it will be pretty simple to translate those steps to Java. If it's not, then your steps were not precise enough or simple enough.

[Kashif Ahmed Khan]

Hi

I have been able to solve it. I was wondering if this could be made better and more cleaner than it is. Choice of some other data structure or way of solving would indeed be interesting.

public class ReverseAString 
{
        
    public synchronized static String reverseString(String content)
    {
        StringBuilder builder = new StringBuilder();
        Map<Integer, Integer> bracketsWithIndex = new HashMap<>();
        
        int startIndexFirstBracket;
        int startIndexSecondBracket;
        int endIndexSecondBracket;
        int endIndexFirstBracket;
        int key = 0;
        int start = 0;
                
        int bracketCount = populateBracketsWithIndexMap(content, key, bracketsWithIndex);
        
        if(bracketCount % 2 != 0)
        {
            String message = "Invalid brackets in the string!" + "\n" + "Bracket Count: " + bracketCount;
            throw new IllegalArgumentException(message);
        }      
        
        if(bracketCount == 2)
        {
            startIndexFirstBracket = bracketsWithIndex.get(key++);
            endIndexFirstBracket = bracketsWithIndex.get(key);
            
            if(startIndexFirstBracket == 0)
            {
                keepOriginalString(startIndexFirstBracket + 1, endIndexFirstBracket, content, builder);
            }
            else
            {
                reverseString(content.length() - 1 , endIndexFirstBracket + 1, content, builder);
                keepOriginalString(startIndexFirstBracket + 1, endIndexFirstBracket, content, builder);
                reverseString(startIndexFirstBracket - 1, start, content, builder);
            }
        }
        else if (bracketCount == 4)
        {
            startIndexFirstBracket = bracketsWithIndex.get(key++);
            startIndexSecondBracket = bracketsWithIndex.get(key++);
            endIndexSecondBracket = bracketsWithIndex.get(key++);
            endIndexFirstBracket = bracketsWithIndex.get(key);

            reverseString(content.length() - 1, endIndexFirstBracket + 1 , content, builder);
            keepOriginalString(startIndexFirstBracket + 1, startIndexSecondBracket, content, builder);
            reverseString(endIndexSecondBracket - 1, startIndexSecondBracket + 1, content, builder);
            keepOriginalString(endIndexSecondBracket + 1, endIndexFirstBracket, content, builder);
            reverseString(startIndexFirstBracket - 1, start, content, builder);            
        }
        return builder.toString();        
    }

    private static int populateBracketsWithIndexMap(String content, int key, Map<Integer, Integer> bracketsWithIndex) 
    {        
        int bracketCount = 0;        
        for(int i = 0; i < content.length(); i++)
        {
            if(content.charAt(i) == '[')
            {
                bracketCount++;
                bracketsWithIndex.put(key++, i);
            }
            else if (content.charAt(i) == ']')
            {
                bracketCount++;
                bracketsWithIndex.put(key++, i);
            }
        }
        return bracketCount;
    }

    private static void reverseString(int startIndex, int endIndex, String content, StringBuilder builder) 
    {
        for(int i = startIndex; i >= endIndex; i--)
        {
            builder.append(content.charAt(i));
        }
    }

    private static void keepOriginalString(int startIndex, int endIndex, String content, StringBuilder builder) 
    {
        for(int i = startIndex; i < endIndex ; i++)
        {
            builder.append(content.charAt(i));
        }
    }
}