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.
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):
import Data.List lstuc :: Eq a => [a] -> [a] lstuc xs = foldr (\x a -> if length x > length a then x else a) [] [concat $ a:b:takeWhile (flip elem [head a, head b] . head) cs | (a:b:cs) <- tails $ group xs]Here is a O(N) solution written in C#:
public static string GetLongestSubset(string str) { if (str == null) throw new ArgumentNullException ("str"); if (str.Length == 0) return String.Empty; int s1 = 0, s2 = 0; // Get next unique char for(int i = 1; i < str.Length; i++) { if (str [i] != str[s1]) { s2 = i; break; } } if (s2 == 0) return str; // all chars are the same int sequenceStart = 0; int maxStart = 0, maxEnd = 0; int maxDiff = 0; // Scan for longest sequences for (int i = s2 + 1; i < str.Length; i++) { // Can this new char belong to the current substring we are building up? if (str [i] != str [s1] && str [i] != str [s2]) { int diff = i - sequenceStart; if (diff >= maxDiff) { maxDiff = diff; maxStart = sequenceStart; maxEnd = i - 1; } if (s1 > s2) { sequenceStart = s1; s2 = i; } else { sequenceStart = s2; s1 = i; } } else if (str [i] != str [i - 1]) { // Track start of each char sequence containing the same char if (str [i] == str [s1]) { s1 = i; } else { s2 = i; } } } int lastDiff = str.Length - sequenceStart; if (lastDiff >= maxDiff) { maxDiff = lastDiff; maxStart = sequenceStart; maxEnd = str.Length - 1; } return str.Substring (maxStart, (maxEnd - maxStart) + 1); }Just because I like regular expressions:
A Perl try (again with regex):
sub max2substr { my @chars = split "", (my $input = shift); reduce { length $b >= length $a ? $b : $a } grep { defined } map { $input =~ /((?:$_){2,})/ } map { join "", @chars[$_..$_+1] } (0..$#chars-1); }[…] 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: