Longest Substring Of Two Unique Characters
June 11, 2013
I wrote today’s exercise as an excuse to illustrate the sets of the previous exercise. We use two loops to form every possible substring, and for each substring enter all the characters into a set, then count the characters:
(define (two-char str)
(let ((longest "") (len 0) (n (+ 1 (string-length str))))
(do ((i 0 (+ i 1))) ((= i n) longest)
(do ((j (+ i 1) (+ j 1))) ((= j n))
(when (and (<= (count (substring str i j)) 2)
(<= len (- j i -1)))
(set! longest (substring str i j))
(set! len (- j i -1)))))))
That uses an auxiliary function to count the number of unique characters in a string; each character is inserted into a set, and the size of the set is returned at the end of the string:
(define (count str)
(let loop ((cs (string->list str)) (s (make-set 29)))
(if (null? cs) (s 'size)
(loop (cdr cs) (s 'adjoin (car cs))))))
Here are some examples:
> (two-char "abcabcbcbc")
"bcbcbc"
> (two-char "abababcabc")
"ababab"
> (two-char "abcacacabc")
"cacaca"
That algorithm is O(n2); there are better algorithms, but I’ll leave those to you in the comments. You can run the program at http://programmingpraxis.codepad.org/ybpvp6gv.
[…] 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:
A long-winded solution in Python:
import itertools
def sub448(s):
ln = len(s)
if ln % 2 == 1:
s += ‘x’