CODEWITHSUNDEEP
javaalgorithm
MK97
MK97

Reputation: 13

Better way to find the most common string in an array using only .get() and .size() methods

I need to find the string with most duplicates in an alphabetically ordered array list. It's a custom ArrayList so I can only use the .get() and .size() methods for the array. Also if two or more strings are equally common, return the one that comes earliest.

This is what I have right now and it works, but I wanted to ask if there is a simpler method that doesn't use a second array list. Speed is also important factor here, so I'm aiming at O(n) complexity.

public String mostCommon(StringList a) {
    ArrayList<String> a2 = new ArrayList<>();
    int max = 0;
    for (int i = 0; i < a.size(); i++) {

        if (i == a.size() - 1) { //last line in the array is an empty line so we break the loop
            break;
        }

        int count = 1; //checks current string against the next ones
        int frequency = 0;

        while (a.get(i).equals(a.get(i + count))) {
            count++;
            frequency++;
        }

        if (frequency > max) {
            max = frequency;
            a2.add(a.get(i));
        }

    }
    return a2.get(a2.size() - 1);
}

Also, the last line in the array is an empty line. Thanks in advance.

Upvotes: 1

Views: 957

Answers (1)

john16384
john16384

Reputation: 8044

You said the List is already sorted, so instead of the best counts of strings found so far (the a2 List is redundant really), why not just count the longest sequence of the same string and remember that one until you find one that exceeds the best count so far:

public String mostCommon(StringList a) {
    String previous = null;
    int bestCount = 0;
    int count = 1;
    String bestString = null;

    for (int i = 0; i < a.size(); i++) {
        if (a.get(i).equals(previous)) { 
            count++;
        }
        else {
            count = 1;
        }

        if (count > bestCount) {
            bestCount = count;
            bestString = a.get(i);
        }

        previous = a.get(i);
    }

    return bestString;
}

Upvotes: 3

Related Questions