Problem17.js

// Problem 17
//
// This problem was asked by Google.
//
// Suppose we represent our file system by a string in the following manner:
//
// The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
//
// dir
//     subdir1
//     subdir2
//         file.ext
//
// The directory dir contains an empty sub-directory subdir1
// and a sub-directory subdir2 containing a file file.ext.
//
// The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:
//
// dir
//     subdir1
//         file1.ext
//         subsubdir1
//     subdir2
//         subsubdir2
//             file2.ext
//
// The directory dir contains two sub-directories subdir1 and subdir2.
// subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1.
// subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.
//
// We are interested in finding the longest (number of characters) absolute path to a file within our file system.
// For example, in the second example above, the longest absolute path is
// "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).
//
// Given a string representing the file system in the above 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.
//
// Note:
//
// The name of a file contains at least a period and an extension.
//
// The name of a directory or sub-directory will not contain a period.
//
// https://leetcode.com/problems/longest-absolute-file-path/description/
//
// O(N) Time Complexity
// O(N) Space Complexity
// N is the length of the fileSystem

/**
 * Returns the longest absolute path to a file given a file system
 * @param {string} fileSystem
 * @return {string}
 */
function longestFilePath(fileSystem) {
  // \n and \t are considered one character

  // key: level, value: the longest folder length at this level
  // By default, we start level 0 with length of 0, and dir to be level 1
  // and dir under dir is at level 2
  const levels = new Map();
  levels.set(0, 0);
  let longest = 0;
  const files = fileSystem.split('\n'); // folders are considered files

  // Could have used an array of length files + 1 instead of a map

  for (let i = 0; i < files.length; i++) {
    const file = files[i];
    // if there is no last index of, it returns -1 and we add 1 to turn to 0
    const level = file.lastIndexOf('\t') + 1; // the amount of \t determines its level
    const fileLength = file.length - level;

    if (file.includes('.')) {
      // actual file
      longest = Math.max(longest, levels.get(level) + fileLength);
    } else {
      const lastLevel = levels.get(level);
      levels.set(level + 1, lastLevel + fileLength + 1); // plus 1 includes the '/' for each level
      // do not have the find the max length for each level because the file system goes down level by level
      // Once we're done with one folder, we go to the second folder and update it's length at that level
    }
  }
  return longest;
}

export default longestFilePath;