## Longest Substring Of Two Unique Characters

### June 11, 2013

Today’s exercise comes from our unending list of interview questions:

Find the longest run of consecutive characters in a string that contains only two unique characters; if there is a tie, return the rightmost. For instance, given input string

`abcabcabcbcbc`

, the longest run of two characters is the 6-character run of`bcbcbc`

that ends the string.

Your task is to write the requested program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

[…] today’s Programming Praxis exercise, our goal is to find the longest substring consisting of only two […]

My Haskell solution (see http://bonsaicode.wordpress.com/2013/06/11/programming-praxis-longest-substring-of-two-unique-characters/ for a version with comments):

Here is a O(N) solution written in C#:

Just because I like regular expressions:

A Perl try (again with regex):

[…] Question is from here. […]

[…] Question is from here. […]

My java solution here.

efficient O(n) solution in haskell:

{-# LANGUAGE BangPatterns #-}

import qualified Data.ByteString as B

loop !_ _ _ _ _ (kmax,imax) !s | B.null s = (kmax,imax)

loop i n k a b (kmax,imax) s

| B.head s == a = cont (n+1) (k+1) a b

| B.head s == b = cont 1 (k+1) b a

| otherwise = cont 1 (n+1) (B.head s) a

where

cont !n’ !k’ !a’ b’ =

if k’ >= kmax

then loop (i+1) n’ k’ a’ b’ (k’,i) (B.tail s)

else loop (i+1) n’ k’ a’ b’ (kmax,imax) (B.tail s)

findLongest :: B.ByteString -> B.ByteString

findLongest b =

case loop 0 0 0 0 0 (0,0) b of

(k,i) -> B.take k . B.drop (i-k+1) $ b

In Javascript:

function substring(str) {

var myString = str;

var count = 0;

var returnStr = “”;

for (var i = 0; i = count) {

count = tempCount;

returnStr = tempReturnStr.join(“”);

}

}

}

return returnStr;

}

alert(substring(“abcabcabcbcbc”));

Sorry… post fail. Clearly time to go to bed.

http://jsfiddle.net/z92aY/

Here’s an O(n) solution: