CODEWITHSUNDEEP
javastring
Shirish Herwade
Shirish Herwade

Reputation: 11711

Longest String With Chars Palindrome

Problem description from school assignment Longest String With Palindrome

I'm getting complexity O(N^2). How can I achieve O(N*log(N))**

My code

int maxL = 0;
    for (int i = 0; i < S.length(); i++) {
        String currentString = String.valueOf(S.charAt(i));
        for (int j = i + 1; j < S.length(); j = j + 1) {
            String jStr = String.valueOf(S.charAt(j));
            if (currentString.contains(jStr)) {
                currentString = currentString.replace(jStr, "");
                int len = j - i + 1;
                if (currentString.length() == 0 && maxL < len) {
                    maxL = len;
                }
            } else {
                currentString = currentString + jStr;
            }
        }
    }
    return maxL;

Upvotes: 0

Views: 78

Answers (1)

Henry
Henry

Reputation: 43798

This problem can be solved in O(n) time using O(n) space. The following algorithm uses a bit set to keep track of the unbalanced characters for the substrings starting at the beginning of the given string. It makes a single pass through the string and remembers the states it has already seen in a hash map. Whenever we see the same state a second time, we have found a valid password: just remove the old shorter substring from the beginning of the current substring.

private static int index(char c) {
    if (c < '0') throw new IllegalArgumentException("illegal char");
    if (c <= '9') return c - '0';
    if (c < 'a') throw new IllegalArgumentException("illegal char");
    if (c <= 'z') return c - 'a' + 10;
    throw new IllegalArgumentException("illegal char");
}

private static int solution(String s) {
    HashMap<BitSet, Integer> states = new HashMap<>();
    int longest = 0;
    BitSet state = new BitSet();
    states.put((BitSet) state.clone(), 0);
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        state.flip(index(c));
        Integer seenAt = states.get(state);
        if (seenAt != null) {
            int len = i - seenAt + 1;
            if (len > longest) longest = len;
        } else {
            states.put((BitSet) state.clone(), i + 1);
        }
    }
    return longest;
}

Upvotes: 1

Related Questions