Find longest series of ones in a binary digit array

Question

How would I find the longest series of ones in this array of binary digits - 100011101100111110011100

In this case the answer should be = 11111

I was thinking of looping through the array and checking every digit, if the digit is a one then add it to a new String, if its a zero re-start creating a new String but save the previously created String. When done check the length of every String to see which is the longest. I'm sure there is a simpler solution ?

Answer 1

Your algorithm is good, but you do not need to save all the temporary strings - they are all "ones" anyway.

You should simply have two variables "bestStartPosition" and "bestLength". After you find a sequence of "ones" - you compare the length of this sequence with saved "bestLength", and overwrite both variables with new position and length.

After you scanned all array - you will have the position of the longest sequence (in case you need it) and a length (by which you can generate a string of "ones").

Answer 2

Java 8 update with O(n) time complexity (and only 1 line):

int maxLength = Arrays.stream(bitStr.split("0+"))
  .mapToInt(String::length)
  .max().orElse(0);

See live demo.

This also automatically handles blank input, returning 0 in that case.

---

Java 7 compact solution, but O(n log n) time complexity:

Let the java API do all the work for you in just 3 lines:

String bits = "100011101100111110011100";

LinkedList<String> list = new LinkedList<String>(Arrays.asList(bits.split("0+")));
Collections.sort(list);
int maxLength = list.getLast().length(); // 5 for the example given

How this works:

1. bits.split("0+") breaks up the input into a String[] with each continuous chain of 1's (separated by all zeros - the regex for that is 0+) becoming an element of the array
2. Arrays.asList() turns the String[] into a List<String>
3. Create and populate a new LinkedList from the list just created
4. Use collections to sort the list. The longest chain of 1's will sort last
5. Get the length of the last element (the longest) in the list. That is why LinkedList was chosen - it has a getLast() method, which I thought was a nice convenience

For those who think this is "too heavy", with the sample input given it took less than 1ms to execute on my MacBook Pro. Unless your input String is gigabytes long, this code will execute very quickly.

EDITED

Suggested by Max, using Arrays.sort() is very similar and executes in half the time, but still requires 3 lines:

String[] split = bits.split("0+");
Arrays.sort(split);
int maxLength = split[split.length - 1].length();