0

I'm currently working on a problem in code hunt level 6.02 which asks me to capitalize every other letter in a String. I have tried doing it with toCharArray + StringBuilder in for loops. It works, but it's not good enough. I still can't get the perfect score for the problem. I'm running out of ideas. Any help will be greatly appreciated.

Note: This is my first post on stack overflow. So if I miss anything or ask question in a wrong way. Pls feel free to point it out for me. Thx.

s is the input string

Attempt 1:

    char [] words = s.toCharArray();
    for (int i = 0; i < words.length; i +=2){
        words[i] = Character.toUpperCase(words[i]);
    }
    return new String(words);

Attempt 2:

    StringBuilder result = new StringBuilder(s);
    for (int i = 0; i < result.length(); i +=2){
        result.replace(i, i + 1, result.substring(i,i + 1).toUpperCase());
    }
    return result.toString();

Input: "iaiaa"

Expected output: "IaIaA"

9
  • 1
    Post the code that you have. The inherent complexity of this problem is O(n/2), which should be the complexity of your solution given that its implemented correctly. Commented Mar 9, 2015 at 1:19
  • 1
    You have looped through half the characters in the words twice. The best solution can't be faster than O(n/2); that is the inherent complexity of the problem. Your solution isn't O(n/2), though because you look through half the words, twice, so your solution is O(n/2 + n/2) Commented Mar 9, 2015 at 1:56
  • 1
    there is something weird going wrong. You HAVE to go through every 2nd character in order to capitalize them. Therefore, the efficiency cannot get any better than O(n/2), which is what you have above... Commented Mar 9, 2015 at 3:03
  • 1
    "Attempt 1" should work and should be about the fastest you can do.
    – Hot Licks
    Commented Mar 9, 2015 at 3:15
  • 1
    The only to be much faster would be to cheat and assume ASCII alphabetics only and AND off the 0x20 bit in every other char.
    – Hot Licks
    Commented Mar 9, 2015 at 3:19

2 Answers 2

0

In both of your attempts, you're going through the characters 2 1/2 times.

Taking your second attempt;

StringBuilder result = new StringBuilder(s);
for (int i = 0; i < result.length(); i +=2){
    result.replace(i, i + 1, result.substring(i,i + 1).toUpperCase());
}
return result.toString();

The first line copies all the characters, and your last line copies all the characters. Your for loop goes through half the characters, for a total of 2 1/2 sets of characters.

I don't know if this is faster, but here's my attempt.

String r = "";
for (int i = 0; i < s.length; i++) {
    if (i % 2 == 0) {
        r += s.substring(i, i + 1).toUpperCase();
    } else {
        r += s.substring(i, i + 1);
    }
}
return r;

I realize that this looks like a lot of intermediate Strings are created, but string concatenation has improved since Java 1.7.

0

I don't know how efficient this really is, but this does the trick for capitalizing the first letter and every other letter after.

    String sentence = "i want to manipulate this string";
    char[] array = new char[] {};

    array = sentence.toCharArray(); //put the sentence into a character array

    for (int i = 0; i < array.length; i += 2) {
        if (array[i] == ' ') { //if the character is blank, move to the next index
            i++;
        }
        array[i] = Character.toUpperCase(array[i]); //capitalize

    }

    sentence = new String(array); //revert array back to String
    System.out.println(sentence); //display

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.