Binary String(01010.....) Problem

Given a string of 0s and 1s. How do one find the maximum length of the substring in which number 开发者_运维问答of 0s and 1s is equal.

Seeing as you're looking for the longest string that matches the criteria, a reasonable algorithm would be:

start with whole string
does string match criteria?
yes: we're done
no:
  (1) find all sub strings of length (whole string - 1)
  do any of these match the criteria?
  yes: we're done
  no:
    repeat from (1) but use (whole string - 2), then (whole string - 3), etc until sub string length is 2

Note that a string of odd length can never match the required criteria so you can reduce the amount of work the program does.

Your next question no doubt will be 'How do I do this in C' and that is where you need to do some work first (assuming this is homework, which it does look like). You won't get 'teh codez' from here. However, if you post some code that doesn't work as expected, you'll get lots of helpful advice to guide you to the correct solution.

Here is another idea that might have a faster run time than those mentioned earlier.

1. You have your string of 1's and 0's.
2. Keep a variable "number_ones" for the number of 1's present in the string
3. Keep another variable (optional) of the string's original length
4. base case: initialize number_ones to the current amount of 1's present in the string
5. If number_ones * 2 == the string's length, you got it, return
6. else we have to shorten the string
7. Check if the character that we dropped is either a one or a zero. If it's a one, subtract 1 from "number_ones", else if it's a zero, leave everything as is.
8. Check if number_ones * 2 == the original string's length - n (n in this case being 1, and increasing afterwards by 1 every time there is missmatch)
9. Repeat steps 6-8 until conditional is true.

To me, CS is all about being creative, and finding new, faster ways to solve obvious problems. This way will save you time in that you will only have to iterate thru the string once, and afterwards just check the next char that's going to be cut. This might not be the best way out there, but hope it helps!

Here's an idea: place counter objects in between every number in your list. Now, for each of these objects, if they have neighbors that are not equal (0 and 1, or 1 and 0) then remove the neighbors, increment the object's counter, and merge it with its neighboring counter objects. You will have to do this for O(n) objects a total of O(n) times, for O(n^2) complexity.

We can improve this to linear time by considering the new neighbors of a counter object whenever it gets new neighbors (it "eats" up its current neighbors when it finds a match.)

Here's an example. I'll use X to denote a 0 on the binary string, and Y to denote a 1, with numbers for the counter objects' current values:

Initial string:

X0X0X0Y0X0X0Y0Y0Y0X0X0Y

First "hit":

X0X0 X0Y 0X0X0Y0Y0Y0X0X0Y -> X0X 1 X0X0Y0Y0Y0X0X0Y

Second "hit":

X0X1X0 X0Y 0Y0Y0X0X0Y -> X0X1X 1 Y0Y0X0X0Y -> X0X 3 Y0X0X0Y -> X 4 X0X0Y

Third "hit":

X4X0 X0Y -> X4X1

No more hits. You now iterate through all the counters one more time and find the max, 4 (pairs) -> length 8, starting at index 1.