CODEWITHSUNDEEP
javapythonalgorithm
Aniruddh Chaturvedi
Aniruddh Chaturvedi

Reputation: 649

Find the length of the longest substring with no consecutive repeating characters

In a recent interview, I was asked this to find the length of the longest sub-string with no consecutive repeating characters. This is different from the standard question, since it considers only consecutive repeating characters.

For example : 

WOOD : 2

Italics : 7

This, of course, has to be done in O(N) time and space.

Upvotes: 1

Views: 568

Answers (4)

Kaveesh Kanwal
Kaveesh Kanwal

Reputation: 1763

Hope the below code helps you. Thanks.

import java.util.HashSet;

public class SubString {
    public static String subString(String input){

        HashSet<Character> set = new HashSet<Character>();

        String longestOverAll = "";
        String longestTillNow = "";

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);

            if (set.contains(c)) {
                longestTillNow = "";
                set.clear();
            }
            longestTillNow += c;
            set.add(c);
            if (longestTillNow.length() > longestOverAll.length()) {
                longestOverAll = longestTillNow;
            }
        }

        return longestOverAll;
    }

    public static void main(String[] args) {
        String input = "kaveeshkanwal abcvdghytrqp";//"substringfindout";
        System.out.println(subString(input));
    }
}

Upvotes: 0

Mohsen Kamrani
Mohsen Kamrani

Reputation: 7457

public static void main(String[] args){
    String s = "italics";
    char[] c = s.toCharArray();
    int tmp = 1;
    for (int i = 1; i < s.length(); i++) {
        if (c[i] == c[i-1]){
            tmp = 0;
            continue;
        }
        tmp++;
    }
    System.out.println(tmp);
}

output = 1

s = "italics"

output = 7

Upvotes: 0

jonrsharpe
jonrsharpe

Reputation: 121975

In Python, I would approach it like this:

def interview(s):
    current = longest = 0
    for index, char in enumerate(s):
        if index and char == s[index - 1]:
            longest, current = max(longest, current), 0
        current += 1
    return max(longest, current)

Upvotes: 2

Slartibartfast
Slartibartfast

Reputation: 1623

Go down the string character by character. Keep track of how many characters you've advanced without hitting a repeat in a var say "repeatcounter". If the next character matches the current character record the counter in a separate variable (only if it's bigger than what's already in there) and reset the repeatcounter.

Upvotes: 3

Related Questions