Marketo Interview Question: Find the longest substring wi... | Glassdoor

Interview Question

Software Engineer Interview(Student Candidate)

Find the longest substring with only two unique characters

  with time complexity O(n).
Tags:
algorithm
Answer

Interview Answer

1 Answer

0

public int longest(String s) {
    int start = 0, end1 = -1, end2 = -1, res = Integer.MIN_VALUE;
    for(int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if(end1 == -1 || c == s.charAt(end1)) end1 = i;
      else if(end2 == -1 || c == s.charAt(end2)) end2 = i;
      else {
        if(end1 < end2) {
          res = Math.max(res, end2 - start + 1);
          start = end1 + 1;
          end1 = -1;
        } else {
          res = Math.max(res, end1 - start + 1);
          start = end2 + 1;
          end2 = -1;
        }
      }
    }
    return Math.max(res, Math.max(end1, end2) - start + 1); //c == s.len-1, still need count
  }

Anonymous on Aug 15, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.