Validate string based on alternative 0's and 1's

Question

I am trying to write a method that takes string as input and gives output as valid number of sub strings that can be produced from it, the string will have only 0's and 1's, sub strings formed will only be of length even.

Valid Sub String Scenario:

The sub string is valid only with consecutive 0's and 1's

Sample Input:

Lets say we have a string 00110, the sub strings we get from this are 00,01,11,10,0011,0110(only even length odd length sub strings are not valid like 001,011,110) out of these only these sub strings are valid 01,10,0011 which have consecutive 0's and 1's

So the output in the above case is 3.

Conditions: Input string length will be under 5<n<10^5

I'm stuck at validating the sub strings,tried couple of different approaches but no success, please let me know if the question need more clarification.

Code:

 public static int counting(string s)
        {
      //make into substrings function
        var substrs = SubStrings(s);

        foreach (var str in substrs.ToList())
        {
            if (!IsValidStr(str))
                substrs.Remove(str);
        }
        var validstr=substrs.Distinct();

        return validstr.Count();
    }

 private static List<string> SubStrings(string s)
    {
        List<string> substrs = new List<string>();

        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 2; j < s.Length; j += 2)
            {
                if ((s.Length - i >= j))
                {
                    substrs.Add(s.Substring(i, j));
                }
            }

        }
        return substrs;
    }

Show source
| validation   | c#   | string   | dynamic-programming   2017-01-05 17:01 1 Answers

Answers to Validate string based on alternative 0&#39;s and 1&#39;s ( 1 )

  1. 2017-01-05 17:01

    This function will validate your substrings, which I believe is what you are asking for help with.

    My understand is that the substring must have at least one 1 and one 0. And that they must be grouped consecutively.

    The concept is basically to loop the numbers are check if they change more than once. Then finally we check to ensure if has changed once.

    bool IsValidSubstring(string s)
    {
        // Check for a valid length substring.
        if(s.Length == 0 || s.Length % 2 != 0)
            return false;
    
        // Loop each character and make sure it doesn't change more than once.
        char last = s[0];
        bool hasChanged = false;
        for(var c in s)
        {
            // Check for a change in character.
            if(c != last)
            {
                // If it has already changed once, then it's invalid.
                if(hasChanged)
                    return false;
                hasChanged = true;
            }
            last = c;
        }
    
        // If we get here, the only thing left to check is that it has changed at least once.
        return hasChanged;
    }
    

    This function will return true for: 01,10,0011 and false for: 00,11,0110 which is what you have asked for.

Leave a reply to - Validate string based on alternative 0's and 1's

◀ Go back