[LeetCode] Longest Absolute File Path

Problem: Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture:

Here, we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file file2.ext.

In text form, it looks like this (with ⟶ representing the tab character):

dir

⟶ subdir1

⟶ ⟶ file1.ext

⟶ ⟶ subsubdir1

⟶ subdir2

⟶ ⟶ subsubdir2

⟶ ⟶ ⟶ file2.ext

If we were to write this representation in code, it will look like this: "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext". Note that the '\n' and '\t' are the new-line and tab characters.

Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by '/'s. Using the above example, the absolute path to file2.ext is "dir/subdir2/subsubdir2/file2.ext". Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces.

Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Example:

Input: input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
Output: 20
Explanation: We have only one file, and the absolute path is "dir/subdir2/file.ext" of length 20.

Approach: If you see it looks like a tree. To get the maximum path length, you need to do DFS to get all the paths and return the path which has the longest length. I am doing the same without making the tree. My approach performed better than 98.53% of C# submissions.

Implementation in C#:

        public static int LengthLongestPath(string input)

        {

            string[] paths = input.Split('\n');

            int maxPathLength = 0;

            List<int> pathLengths = new List<int>();

            for (int i = 0; i < paths.Length; ++i)

            {

                int count = paths[i].Count(ch => ch == '\t');

                if (count > pathLengths.Count - 1)

                {

                    if (count == 0)

                    {

                        pathLengths.Add(paths[i].Length);

                    }

                    else

                    {

                        pathLengths.Add(paths[i].Substring(paths[i].LastIndexOf('\t') + 1).Length + pathLengths[count - 1] + 1);

                    }

                }

                else

                {

                    if (count == 0)

                    {

                        pathLengths[count] = paths[i].Length;

                    }

                    else

                    {

                        pathLengths[count] = paths[i].Substring(paths[i].LastIndexOf('\t') + 1).Length + pathLengths[count - 1] + 1;

                    }

                }

                if (paths[i].Contains('.'))

                {

                    maxPathLength = Math.Max(maxPathLength, pathLengths[count]);

                }

            }

            return maxPathLength;

        }

Complexity: ?