C # - code optimization to get all substrings from a string

Question

I worked on a code snippet to get all the substrings from a given string.

Here is the code I'm using

 var stringList = new List<string>();
 for (int length = 1; length < mainString.Length; length++)
 {
    for (int start = 0; start <= mainString.Length - length; start++)
    {
       var substring = mainString.Substring(start, length);
       stringList.Add(substring);
    }
 }

I think this is not so cool, with two for loops. Is there any other way that I can achieve this with better time complexity.

I’m stuck in the fact that I need two loops to get a substring. Is there any other way I can peek?

Answer 1

The number of substrings in a string O(n^2), so one loop inside another is the best you can do. You are right in your code structure.

Here is how I would formulate your code:

void Main()
{
    var stringList = new List<string>();
    string s = "1234";
    for (int i=0; i <s.Length; i++)
        for (int j=i; j < s.Length; j++)
            stringList.Add(s.Substring(i,j-i+1));
}

Answer 2

You need 2 forloops

Demo here

var input = "asd sdf dfg";
var stringList = new List<string>();

for (int i = 0; i < input.Length; i++)
{
    for (int j = i; j < input.Length; j++)
    {
        var substring = input.Substring(i, j-i+1);
        stringList.Add(substring);
    }
}

foreach(var item in stringList)
{
    Console.WriteLine(item);
}

.

, fixed

Answer 3

, . char[] ArraySegment<of char> . .

StringBuilder .NET Microsoft Docs:

String . , System.String, , . , , , String, .

:

static List<ArraySegment<char>> SubstringsOf(char[] value)
{
    var substrings = new List<ArraySegment<char>>(capacity: value.Length * (value.Length + 1) / 2 - 1);
    for (int length = 1; length < value.Length; length++)
        for (int start = 0; start <= value.Length - length; start++)
            substrings.Add(new ArraySegment<char>(value, start, length));
    return substrings;
}

Microsoft Docs, ArraySegment? StackOverflow, ArraySegment <T> MSDN <T> .Capacity MSDN.

Answer 4

Well, O(n**2)time complexity is inevitable, however you can try to use space consumption. In many cases, you do not want all substrings to be implemented, for example, like List<string>:

public static IEnumerable<string> AllSubstrings(string value) {
  if (value == null) 
    yield break; // Or throw ArgumentNullException

  for (int length = 1; length < value.Length; ++length)
    for (int start = 0; start <= value.Length - length; ++start)
      yield return value.Substring(start, length);
}

For example, let us count all the substrings in "abracadabra"starting with aand longer than 3characters. Please note that all we need to do is iterate over the subkeys without saving them in the list:

int count = AllSubstrings("abracadabra")
  .Count(item => item.StartsWith("a") && item.Length > 3);

If for any reason you want List<string>, just add .ToList():

var stringList = AllSubstrings(mainString).ToList();