LeetCode 551 - Student Attendance Record I

The problem gives us a string s where each character represents a student's attendance record for one day. There are only three possible characters: - 'A' means the student was absent. - 'L' means the student was late. - 'P' means the student was present.

leetcodeeasystring

LeetCode Problem 551

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us a string s where each character represents a student's attendance record for one day. There are only three possible characters:

  • 'A' means the student was absent.
  • 'L' means the student was late.
  • 'P' means the student was present.

We must determine whether the student qualifies for an attendance award. The student is eligible only if both conditions are satisfied:

  1. The total number of absences ('A') is strictly less than 2, meaning there can be at most one absence.
  2. The student never has 3 or more consecutive late days ('L').

The input is a single string whose length ranges from 1 to 1000. This constraint is small enough that even a straightforward linear scan is more than fast enough. Since we only need to check two simple conditions, we do not need any advanced data structures or algorithms.

The expected output is a boolean value:

  • Return true if the attendance record satisfies both conditions.
  • Return false otherwise.

Several edge cases are important to think about before implementation. A student may have exactly one absence, which is allowed, but two absences should immediately fail the check. Another important case is consecutive lateness. Two consecutive 'L' characters are acceptable, but three consecutive 'L' characters invalidate the record. It is also possible for the invalid sequence to appear at the beginning, middle, or end of the string, so the algorithm must correctly track consecutive lateness throughout the scan.

Because the input is guaranteed to contain only 'A', 'L', and 'P', we do not need to validate characters or handle malformed input.

Approaches

Brute Force Approach

A brute force solution would explicitly count absences and repeatedly check every possible substring of length 3 to see whether it equals "LLL".

The algorithm would work as follows:

  1. Traverse the string once to count how many 'A' characters appear.
  2. Traverse again and inspect every substring of length 3.
  3. If any substring equals "LLL", return false.
  4. Otherwise, if the absence count is less than 2, return true.

This approach is correct because it directly checks the two rules defined in the problem statement. However, it performs multiple passes over the string and repeatedly creates substrings, which is unnecessary.

Even though the constraints are small enough that this solution would still pass, we can do better with a cleaner single-pass solution.

Optimal Approach

The key observation is that we can verify both conditions simultaneously while scanning the string once from left to right.

We maintain:

  • A counter for total absences.
  • A counter for the current streak of consecutive late days.

As we process each character:

  • If we see 'A', increment the absence count.
  • If we see 'L', increment the consecutive late counter.
  • If we see 'P' or 'A', reset the late streak because the consecutive sequence is broken.

At any point:

  • If absences reach 2, we can immediately return false.
  • If the late streak reaches 3, we can immediately return false.

If we finish the scan without violating either condition, the record is valid.

This works efficiently because each character is processed exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Multiple scans and repeated substring checks
Optimal O(n) O(1) Single pass while tracking absences and late streak

Algorithm Walkthrough

  1. Initialize two variables:
  • absence_count = 0
  • late_streak = 0

The first variable tracks how many times the student was absent. The second variable tracks the number of consecutive late days currently being processed. 2. Traverse the string one character at a time.

Each character represents the attendance status for a single day. 3. If the current character is 'A':

  • Increment absence_count.
  • Reset late_streak to 0.

We reset the late streak because an absence breaks a consecutive sequence of late days. 4. If the current character is 'L':

  • Increment late_streak.

Since the student is late again, the consecutive late sequence continues. 5. If the current character is 'P':

  • Reset late_streak to 0.

Being present breaks any ongoing late streak. 6. After updating the counters, check the failure conditions:

  • If absence_count >= 2, return False.
  • If late_streak >= 3, return False.

We can terminate early because the record is already invalid. 7. If the loop completes without triggering either failure condition, return True.

Why it works

The algorithm maintains two invariants during the scan:

  • absence_count always equals the total number of absences seen so far.
  • late_streak always equals the number of consecutive trailing 'L' characters ending at the current position.

Because these values are updated correctly after every character, the algorithm immediately detects any rule violation. If no violation occurs by the end of the traversal, the attendance record satisfies both requirements.

Python Solution

class Solution:
    def checkRecord(self, s: str) -> bool:
        absence_count = 0
        late_streak = 0

        for ch in s:
            if ch == 'A':
                absence_count += 1
                late_streak = 0
            elif ch == 'L':
                late_streak += 1
            else:
                late_streak = 0

            if absence_count >= 2:
                return False

            if late_streak >= 3:
                return False

        return True

The implementation closely follows the algorithm described earlier. Two integer counters are initialized before the loop begins.

Inside the loop, the current character determines how the counters change:

  • 'A' increases the absence count and resets the late streak.
  • 'L' extends the current late streak.
  • 'P' resets the late streak because the consecutive sequence ends.

After updating the counters, the code immediately checks whether either rule has been violated. Early termination improves efficiency because the algorithm does not continue processing once the answer is already known.

If the loop completes successfully, the function returns True, meaning the attendance record satisfies both conditions.

Go Solution

func checkRecord(s string) bool {
    absenceCount := 0
    lateStreak := 0

    for _, ch := range s {
        if ch == 'A' {
            absenceCount++
            lateStreak = 0
        } else if ch == 'L' {
            lateStreak++
        } else {
            lateStreak = 0
        }

        if absenceCount >= 2 {
            return false
        }

        if lateStreak >= 3 {
            return false
        }
    }

    return true
}

The Go implementation is nearly identical to the Python version. The main difference is syntax.

Go iterates through the string using a for range loop, where ch is a rune. Since the input only contains ASCII characters, comparing against 'A', 'L', and 'P' is straightforward.

No special handling for empty strings is required because the problem guarantees the string length is at least 1.

Worked Examples

Example 1

Input:

s = "PPALLP"

Step-by-step traversal:

Index Character absence_count late_streak Valid?
0 P 0 0 Yes
1 P 0 0 Yes
2 A 1 0 Yes
3 L 1 1 Yes
4 L 1 2 Yes
5 P 1 0 Yes

The student has only one absence and never reaches three consecutive late days.

Result:

true

Example 2

Input:

s = "PPALLL"

Step-by-step traversal:

Index Character absence_count late_streak Valid?
0 P 0 0 Yes
1 P 0 0 Yes
2 A 1 0 Yes
3 L 1 1 Yes
4 L 1 2 Yes
5 L 1 3 No

At index 5, the late streak becomes 3, which violates the rules.

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed exactly once
Space O(1) Only a few integer counters are used

The algorithm performs a single linear traversal of the attendance string. No nested loops or auxiliary data structures are required. The memory usage remains constant regardless of input size because only two counters are maintained.

Test Cases

solution = Solution()

assert solution.checkRecord("PPALLP") == True   # valid example from problem
assert solution.checkRecord("PPALLL") == False  # three consecutive L's

assert solution.checkRecord("P") == True        # single present day
assert solution.checkRecord("A") == True        # single absence allowed
assert solution.checkRecord("L") == True        # single late day allowed

assert solution.checkRecord("AA") == False      # two absences
assert solution.checkRecord("LLL") == False     # exactly three consecutive late days
assert solution.checkRecord("LLLL") == False    # more than three consecutive late days

assert solution.checkRecord("APLPLP") == True   # mixed valid sequence
assert solution.checkRecord("ALALL") == False   # second absence invalidates record

assert solution.checkRecord("LLAPLL") == True   # late streak interrupted
assert solution.checkRecord("PPLLLP") == False  # late streak in middle

assert solution.checkRecord("APAPAPAP") == False  # multiple absences spread apart
assert solution.checkRecord("PLPLPLPL") == True   # alternating late and present

assert solution.checkRecord("LALL") == True     # two late days but not consecutive three
assert solution.checkRecord("ALLL") == False    # valid absence count but invalid late streak
Test Why
"PPALLP" Valid example from the prompt
"PPALLL" Invalid because of three consecutive late days
"P" Smallest valid present-only input
"A" Single absence should still pass
"L" Single late day should pass
"AA" Tests absence limit violation
"LLL" Tests minimum invalid late streak
"LLLL" Tests larger invalid late streak
"APLPLP" Mixed attendance with no violations
"ALALL" Two absences separated by other characters
"LLAPLL" Late streak interrupted correctly
"PPLLLP" Invalid streak in the middle
"APAPAPAP" Multiple separated absences
"PLPLPLPL" Alternating sequence should remain valid
"LALL" Consecutive late count stays below three
"ALLL" Tests simultaneous presence of valid and invalid conditions

Edge Cases

One important edge case is a record with exactly one absence, such as "PPA". Since the condition requires strictly fewer than 2 absences, one absence is still valid. A common mistake is using the wrong comparison operator and rejecting records with exactly one absence. The implementation correctly checks for absence_count >= 2.

Another important edge case is when the late streak appears at the very end of the string, such as "PPALLL". Some implementations incorrectly reset the streak too early or fail to check the final sequence. This solution checks the late streak immediately after every character, so a trailing "LLL" is detected correctly.

A third edge case is interrupted late sequences, such as "LLPLL". Even though there are four total 'L' characters, they are not consecutive. The implementation resets late_streak whenever it encounters 'P' or 'A', ensuring only consecutive late days are counted.

A fourth subtle edge case is when both rules are close to being violated simultaneously, such as "ALLL". The absence count is still valid because there is only one 'A', but the late streak reaches three. The algorithm independently tracks both conditions and correctly returns False as soon as the late streak becomes invalid.