0 
    String input = "AAAB";

    String output = "";
    for (int index = 0; index < input.length(); index++) {
        if (input.charAt(index % input.length()) != input
                .charAt((index + 1) % input.length())) {

            output += input.charAt(index);

        }
    }
    System.out.println(output);

But it doesn't work if my input is "ABABAB" or just "AAAA". Any ideas?

Improve this question
2
  • 2
    I'm not entirely sure what your intent is, could you add examples of input and matching expected output? Commented Dec 13, 2012 at 18:23
  • 1
    You need to define: without using arrays. input.charAt(..) is using an array for example... Commented Dec 13, 2012 at 18:23

5 Answers 5

Reset to default
4

Use a data structure to know if a character has already been found, such as a Set. You can, for instance, use its add() method and check its return value.

Also, you might consider using StringBuilder for repetitive concatenation, it's much more efficient.

Set<Character> characters = new HashSet<Character>();
String input = "AAAB";
StringBuilder output = new StringBuilder();
for (int index = 0; index < input.length(); index++) {
    char character = input.charAt(index);
    if (characters.add(character)) {
        output.append(character);
    }
}
System.out.println(output.toString());
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Ironically using arrays would have been harder.
This is a good idea but im not allowed to use any typ of array, i mean hashset too.
1

Optimized for speed version

public static void main(String[] args) {
    String input = "AAAB";
    StringBuilder output = new StringBuilder();
    for (int i = 0; i < input.length(); i++) {
        if (!contains(output, input.charAt(i))) {
            output.append(input.charAt(i));
        }
    }
    System.out.println(output);
}

private static boolean contains(StringBuilder output, char c) {
    for(int i = 0; i < output.length();  i++) {
        if (output.charAt(i) == c) {
            return true;
        }
    }
    return false;
}
Improve this answer

3 Comments

Wouldn't this be O(n(log n)), on account of the contains method? Using HashSet#add() (O(1)) and going through the String (O(n)) is O(n)
This program works only with primitive chars. Can you imagine the cost of creating an Object for each char? Without testing I can say the difference will be huge.
Actually, it seems like characters in the range \u0000-\u007f are cached when boxing as of 5.1.7. Boxing Conversion of the JLS. Definitely a good point, though. As a side note, as @assylias pointed out in his comment, using a StringBuilder to search for characters could be seen as using an array. But then again, almost any popular data structure (such as HashSet/Map) ends up using arrays :)
0

Let's take a look at what your loop is doing:

if (input.charAt(index % input.length()) != input
  .charAt((index + 1) % input.length()))

1) First of all, you should recognize that you are wasting time and processing power by performing the '% input.length()' operation, because index is ALWAYS going to be less than input.length(), so index%input.length() is always equal to index.

Let's disregard %input.length() going forward.

2) When you compare input.charAt(index) to input.charAt(index+1) you're only comparing the current character against the next one. The original question, if I understood it correctly, asks you to remove ALL duplicates, not just ones that appear next to one another.

3) Your algorithm will most likely throw a IndexOutOfBounds exception because when you reach the end of your string (when index == input.length() - 1) checking input.charAt(index+1) will look one character too far in the String.

As the first answer suggested, you'll want to utilize some form of data structure to store all of the DISTINCT characters you encounter. Any time you hit a new character, you'll want to a) add it to your data structure, and b) add it to the end of your output.

Improve this answer

2 Comments

He's using the modulo just to avoid the IOOB. In this case it would be better letting it happen, because he's comparing the last character to the first.
Yes i did it because i wanted to see if the last element == the first one.
0 
public static void print(String s) {
    List<String> v = new ArrayList<String>();
    for(int j=0; j<s.length(); j++) {
        if(!v.contains("" + s.charAt(j)))
            v.add("" + s.charAt(j));
    }


    for(String e : v)
        System.out.print(e);
}
Improve this answer

1 Comment

Sorry, I deleted the previous one, yes, the previous code printed in order because of the TreeSet, this one keeps original order.
0

(I hope you mean duplicates, not repetitions.)

public static String withoutDuplicates(String s) {
    for (int i = 0; i < s.length(); ) {
        boolean removedDuplicate = false;
        for (int duplicateLength = (s.length() - i) / 2; duplicateLength >= 1; 
                --duplicateLength) {
            if (foundDuplicate(s, i, duplicateLength)) {
                s = s.substring(0, i) + s.substring(i + duplicateLength);
                removedDuplicate = true;
                break;
            }
        }
        if (!removedDuplicate) {
            ++i;
        }
    }
    return s;
}

private static boolean foundDuplicate(String s, int i, int duplicateLength) {
    String sought = s.substring(i, i + duplicateLength);
    return s.indexOf(sought, i + duplicateLength) != -1;
}

Correction: duplicateLength initialisation value was out of range.

Improve this answer

2 Comments

But there is an Error when i use ABCCDA.
That should become BCDA (as always the first duplicate is removed).