Skip to content

388. Longest Absolute File Path 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct T {
  int depth;
  size_t length;
};

class Solution {
 public:
  int lengthLongestPath(string input) {
    size_t ans = 0;
    stack<T> stack{{{-1, 0}}};  // placeholder
    istringstream iss(input);

    for (string token; getline(iss, token, '\n');) {
      const int depth = ranges::count(token, '\t');
      std::erase(token, '\t');
      while (depth <= stack.top().depth)
        stack.pop();
      if (isFile(token))
        ans = max(ans, stack.top().length + token.length());
      else  // directory + '/'
        stack.emplace(depth, stack.top().length + token.length() + 1);
    }

    return ans;
  }

 private:
  bool isFile(const string& token) {
    return token.find('.') != string::npos;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class T {
  public int depth;
  public int length;
  public T(int depth, int length) {
    this.depth = depth;
    this.length = length;
  }
}

class Solution {
  public int lengthLongestPath(String input) {
    int ans = 0;
    Deque<T> stack = new ArrayDeque<>();
    stack.push(new T(-1, 0));

    for (String token : input.split("\n")) {
      final int depth = getDepth(token);
      token = token.replace("\t", "");
      while (depth <= stack.peek().depth)
        stack.pop();
      if (token.contains(".")) // `token` is file.
        ans = Math.max(ans, stack.peek().length + token.length());
      else // directory + '/'
        stack.push(new T(depth, stack.peek().length + token.length() + 1));
    }

    return ans;
  }

  private int getDepth(final String token) {
    return (int) token.chars().filter(c -> c == '\t').count();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def lengthLongestPath(self, input: str) -> int:
    ans = 0
    stack = [(-1, 0)]  # placeholder

    for token in input.split('\n'):
      depth = token.count('\t')
      token = token.replace('\t', '')
      while depth <= stack[-1][0]:
        stack.pop()
      if '.' in token:  # `token` is file.
        ans = max(ans, stack[-1][1] + len(token))
      else:  # directory + '/'
        stack.append((depth, stack[-1][1] + len(token) + 1))

    return ans