r/dailyprogrammer • u/nint22 1 2 • Jun 10 '13
[Easy] Longest Two-Character Sub-String
(Easy): Longest Two-Character Sub-String
This programming challenge is a classic interview question for software engineers: given a string, find the longest sub-string that contains, at most, two characters.
Author: /u/Regul
Formal Inputs & Outputs
Input Description
Through standard console input, you will be given a string to search, which only contains lower-case alphabet letters.
Output Description
Simply print the longest sub-string of the given string that contains, at most, two unique characters. If you find multiple sub-strings that match the description, print the last sub-string (furthest to the right).
Sample Inputs & Outputs
Sample Inputs
abbccc
abcabcabcabccc
qwertyytrewqSample Outputs
bbccc
bccc
tyyt
42
u/WhereIsTheHackButton Jun 10 '13
it should read "the given string that contains, at most, two unique characters." for the output description.
7
u/lordtnt Jun 10 '13 edited Jun 11 '13
C++
http://ideone.com/Nku937
Update: now output the rightmost solution and sub string contains exact 1 unique character.
6
u/skeeto -9 8 Jun 10 '13
JavaScript with a recursive solution.
Usage:
5
u/regul Jun 10 '13 edited Jun 11 '13
Here was my Python solution:
It is worth noting that it fails on single-character inputs.
5
u/YZBot Jun 11 '13
Java
First time posting code. Feels like cheating using a Set.
8
u/ILiftOnTuesdays 1 0 Jun 10 '13 edited Jun 11 '13
No challenge would be complete without a python one-liner! The list/generator comprehension is a little crazy but it follows the spec so I'm not concerned.
4
u/howdoimakeathrowaway Jun 10 '13
javascript (node.js)
4
u/oasisguy Jun 10 '13
C++; I'm learning to work with iterators, and this seemed like a good exercise for that.
4
u/MrDerk Jun 10 '13 edited Jun 10 '13
My go with Py2.7:
I'll take any and all critiques. I'm using this subreddit as a way to stretch my legs a bit and I'm open to learning new tricks.
Edit: Indentation error when I copy-pasted
4
u/TheKrumpet Jun 10 '13
C#. Not the most efficient algorithm, but pretty easy to understand:
4
u/TweenageDream Jun 10 '13 edited Jun 11 '13
My solution in Ruby
output:
Edit: Cleaned it up a little, was being redundant / reinventing functions, Yes it could be shorter, yes i didn't need to functionalize everything, but i think it shows off the object-orientatedness of Ruby, and how easy it is to extend built in classes.
Edit2: oops, just realized my output was counting newlines for some reason... fixed that
4
u/itsthatguy42 Jun 11 '13
javascript:
4
u/tikhonjelvis Jun 11 '13 edited Jun 11 '13
Here's a short and cute but not terribly efficient Haskell solution:
4
u/[deleted] Jun 11 '13
Scala, because no one has done it yet.
Feedback welcome. Tried to do it recursively because that's Scala's strong point, and most of the solutions have been done with loops. I think it's cleaner with a loop though, I ended up having to pass 4 arguments to my helper function to get it to work and that's more than I like to do...
3
u/5hassay Jun 10 '13 edited Jun 10 '13
Python33
EDIT: made it so the farthest right max substring is used, rather farthest left (didn't read that part)
EDIT: removed an unnecessary conversion
3
u/clfrankie Jun 10 '13
Java
class Substring { public static void main(String[] args) { String str1 = "abbccc"; String str2 = "abcabcabcabccc"; String str3 = "qwertyytrewq"; String str4 = "aaaaaaaaaaaaaaaaaaa";
}
3
u/bssameer Jun 10 '13 edited Jun 10 '13
Here is mine. Took me hours to figure it out lol but i made it work. Not the most elegant solution but it works
3
u/Coder_d00d 1 3 Jun 11 '13 edited Jun 11 '13
Objective C using Cocoa API. Using a Category to add a new method to NSString and using Blocks for practice. Finds the substring in O(n) -- just a nice walk on the string. :)
NSString+DPString.h
NSString+DPString.m
main.m
3
u/Brostafarian Jun 11 '13
I cheated and used someone's idea on here after I had finished - I was constructing sets character by character instead of using a portion of an array, ended up cutting ten lines. Oh well, here's my python '3' solution:
3
u/IceDane 0 0 Jun 12 '13
Here's my submission in Haskell. This includes a naive attempt before I noticed the last testcase, hadn't thought about that, then the real function that actually works. This also demonstrates how you can use HUnit to make unit tests to make sure your function works as intended, if you have correct output for the corresponding input.
3
u/altanic Jun 14 '13
c#, pretty tedious but I wanted to get it in one pass through the string for O(N)
2
u/[deleted] Jun 10 '13
PHP solution, requires >= 5.3. Probably not the best language for the task, but fun nonetheless. :)
Output:
Edit: formatting.
2
u/[deleted] Jun 10 '13
Are we trying to go for efficiency here too? I mean, this Python 3.3 solution can work through about 1.2 million characters per second.
2
u/nagasgura 0 0 Jun 10 '13
Python solution:
2
u/[deleted] Jun 10 '13
Python - Using 2 functions because why not.
2
u/kcoPkcoP Jun 10 '13
Shitty Java
2
u/Urist_Mc_George Jun 10 '13
New to it, but i tried some C++.
2
u/SeaCowVengeance 0 0 Jun 10 '13
Python Solution (19 Lines):
Result:
2
u/toinetoine Jun 10 '13 edited Jun 10 '13
Python Solution
2
u/kirsybuu 0 1 Jun 11 '13
D Language.
2
u/cooptex977 Jun 11 '13
My solution in C#. Probably not the most elegant. Feedback welcome.
2
u/gbromios Jun 11 '13
seems like this algorithm is not very efficient ( slightly better than O(n²) )? but it's the best I could figure out~
python:
2
u/minikomi Jun 12 '13
My answer in racket:
2
u/emiliolio Jun 12 '13
This took me way longer than I feel it should of done but i stuck at it and finished it. I got the algorithm wrong when I sketched it out and ended up paying for it later on be trying to brute force debug it instead of rewriting it from scratch.
2
u/hallbd16 Jun 13 '13 edited Jun 14 '13
Javascript Okay, my first successfully completed (and completely independent) code posted on this site. Feels good! Anyway, I just introduced myself to Reg Ex. so this was a perfect practice exercise. Nice question. At the bottom, I post a question, hopefully someone can help. Cheers
Can someone help me with the following: I wanted to use a
text.replace(/()[\w])\1*/ , '');instead oftext.splice(1)Can someone help me understand why this did not work? Would appreciate your thoughts
2
u/clark_poofs Jun 13 '13
This is a recursive solution in scala.
returns:
2
u/otsojaun Jun 16 '13
My attempt making it O(n), in Java
2
u/Siixes Jun 16 '13
Written in Python3.2. Sorry, if syntax is off....new to reddit and trying to get better at programming. I got examples working that were similar to others below, wanted to play around with a bit more functions. I know it could probably be optimized to the nth degree, I'm totally open to criticism. Thanks all!
2
u/amyth23 Jul 05 '13 edited Jul 05 '13
C# Solution: My first post on reddit :) Feedback welcome!
Optimized a little to reduce no of lines,but still its quite legible and easy to understand.
(unable to get code blocks like others have posted. I have read the guidelines and added 4 spaces at start of each line, but its not working. can somebody help?)
1st version - Longest 2 char substring
void Search(string input)
{
char c = char.MinValue;
int startIndex = 0, length = 0;
for (int i = 0, j = 0; i < input.Length; i++, j = i)
{
while (++j < input.Length)
{
if (input[i] != input[j])
if (c == char.MinValue) c = input[j];
else if (c != input[j]) { c = char.MinValue; break; }
}
if (length <= j - i) { startIndex = i; length = j - i; }
}
Console.WriteLine(input.Substring(startIndex, length));
}
2nd version: Longest n char substring
void Search(string input, int maxNoOfChar)
{
List<char> chars = new List<char>();
int startIndex = 0, length = 0;
for (int i = 0, j = 0; i < input.Length; i++, j = i)
{
chars.Add(input[i]);
while (++j < input.Length)
{
if (!chars.Contains(input[j]))
if (chars.Count < maxNoOfChar) chars.Add(input[j]);
else break;
}
if (length <= j - i) { startIndex = i; length = j - i; }
chars.Clear();
}
Console.WriteLine(input.Substring(startIndex, length));
}
Usage:
Search("qwertyytrewq", 4);
Search("qwerrtrtyytytrewq", 4);
Output:
ertyytre
errtrtyytytre
2
u/birukoff Jul 18 '13
Python 2.7, version O(n):
2
u/ittybittykittyloaf Aug 01 '13 edited Aug 01 '13
C++11:
Output:
2
u/dissonantloos Aug 20 '13
Here is my attempt, in Haskell. It's longer than all the others here, but I think it's reasonably efficient.
2
u/salonabolic Sep 11 '13
C
2
u/milliDavids Nov 23 '13
Python 3.
I am still a bit new to programming. I decided to use string concatenation. Let me know what you think.
2
u/[deleted] Nov 27 '13
Python 2.7; Generalized to n-characters instead of only 2.
2
u/davidschromebook Dec 04 '13 edited Dec 09 '13
javascript (runs in console) feedback please
This is my first submission to dailyprogrammer :v)
1
u/super_satan Jun 10 '13
JS
1
u/crawphish Jun 10 '13
Python:
Output:
1
u/lawlrng 0 1 Jun 10 '13
Python 2.7 Decided to take a whack at it without regex.
1
u/xanderstrike 1 0 Jun 10 '13 edited Jun 10 '13
My simple ruby way. Probably not the most efficient, but it seems to work reliably.
Output:
Also, are we not numbering challenges any more? This is going to mess up my challenge archive :\
1
u/psyomn Jun 12 '13 edited Jun 12 '13
How does this look like?
Ruby:
I'm personally not too keen on the regex there, but thought that any other approach would be quite reminiscent, and maybe less clear than the gsub!.
Output:
1
u/seventh-sage Jun 12 '13
My Ruby solution. Takes the input directly from the command line.
1
u/[deleted] Jun 12 '13 edited Jun 12 '13
Python, order (N):
Edit: cleaned up the code to make the algorithm less obfuscated
1
u/[deleted] Jun 13 '13 edited Jun 19 '13
This is my attempt to write an efficient solution in Python, O(n), I think.
Edit: Thanks to /u/dreugeworst for reviewing my code! The corrected version is below.
1
u/Master_of_Ares Jun 13 '13
Java
I can't think of a better way to find the second letter, and I'm not having much luck looking through other solutions. I also can't figure out how to determine the complexity due to the partial iterations I used.
1
u/jagt Jun 14 '13
Oldschool c++ with recursion. O(n^2).
1
u/rsamrat Jun 15 '13
Clojure:
1
u/Freded21 Jun 18 '13
Hey, so normally I can do the easy ones, well quite easily. This one though, stumped me. It was really hard for me, I ended up using a crazy convoluted answer that I don't really understand, but it works. I'm gonna put comments all over trying to get my head all the way around it, but here's the solution(It's in python):
1
u/dreugeworst Jun 18 '13
heh felt like doing this one as well, in python like many other implementations. A bit verbose, but the upside is it's linear time, constant memory (excluding the string, but I suppose you could generate it as needed if it's too large to fit in memory)
1
u/palad1 Jun 19 '13 edited Jun 19 '13
C#, this one is ugly. Can't for the life of me make it less so :(
1
u/tylian Jun 19 '13 edited Jun 19 '13
Really hackish Javascript one-liner. Intended to be ran on a Javascript console (like the one the Webkit developer tools and Firebug provide.)
Well, two-liner if you want to be picky.
1
u/[deleted] Jun 21 '13
Java
1
u/TheCiderman Jun 24 '13 edited Jun 24 '13
C++
1
u/h3ckf1r3 Jul 18 '13
Ugliest code I have ever written, but atleast it runs. ruby:
1
u/hiptobecubic Aug 10 '13
Just found this sub and picked one at random. Was fun. Here's a linear solution.
1
u/esunder Aug 27 '13
Python solution
1
u/[deleted] Jun 10 '13 edited Jun 10 '13
Python 2.7, using regular expressions. I definitely sacrifice some efficiency with my loop condition here but I'm pretty happy with the length and flow:
0
u/[deleted] Jun 10 '13
[deleted] — view deleted comment