bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Hard1-D Dynamic ProgrammingLC 552

Student Attendance Record II

An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters: 'A': Absent. 'L': Late. 'P': Present. Any student is eligible for an attendance award if they meet both of the following criteria: The student was absent ('A') for strictly fewer than 2 days total. The student was never late ('L') for 3 or more consecutive days. Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7.

Asked at 2 companies
GoogleUber
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode