#551

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Student Attendance Record I

Determine if a student's attendance record qualifies for an award based on specific criteria for absences and lateness.

Problem Statement

You are given a string s representing a student's attendance record, where each character signifies whether the student was absent, late, or present on a particular day. The record can only contain the following characters: 'A' (absent), 'L' (late), and 'P' (present).

A student is eligible for an attendance award if they meet two conditions: having fewer than two 'A' characters, and no occurrence of three consecutive 'L' characters. Return true if the student is eligible, otherwise return false.

Examples

Example 1

Input: s = "PPALLP"

Output: true

The student has fewer than 2 absences and was never late 3 or more consecutive days.

Example 2

Input: s = "PPALLL"

Output: false

The student was late 3 consecutive days in the last 3 days, so is not eligible for the award.

Constraints

1 <= s.length <= 1000
s[i] is either 'A', 'L', or 'P'.

Solution Approach

Check Absences

Iterate through the string to count the number of 'A' characters. If the count exceeds 1, return false immediately. This operation has a time complexity of O(n), where n is the length of the string.

Check Consecutive Lateness

During the iteration, also check for consecutive 'L' characters. If three consecutive 'L' characters are found, return false. This check can be done while counting the absences in one linear scan of the string.

Return Result

If the number of absences is within the allowed limit and no three consecutive 'L's are found, return true. If either condition fails, return false. The solution works in linear time, O(n).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n), where n is the length of the string, since we need to process each character in the string exactly once. The space complexity is O(1) as we only need a few variables to store the count of absences and track consecutive 'L's.

What Interviewers Usually Probe

Candidate correctly identifies the need for a linear scan of the string.
Candidate efficiently handles the dual check for both 'A' count and 'L' streaks in one pass.
Candidate demonstrates awareness of optimal time complexity for this problem.

Common Pitfalls or Variants

Common pitfalls

Failing to handle edge cases where the string contains less than three characters.
Not returning early if the number of absences exceeds 1 or three consecutive 'L's are detected.
Overcomplicating the solution with unnecessary operations, leading to higher time or space complexity.

Follow-up variants

Check for exactly one absence or at least two consecutive late days.
Determine eligibility based on a maximum of two absences and no 'L' streaks longer than two days.
Extend the logic to check for a specific number of tardies (e.g., exactly one day late allowed).

FAQ

How do I approach solving the Student Attendance Record I problem?

Focus on efficiently counting the number of absences and checking for three consecutive late days, both of which can be done in a single pass through the string.

What are the main conditions for the attendance award?

The student needs fewer than two absences and no streak of three consecutive late days.

What is the time complexity of solving this problem?

The time complexity is O(n), where n is the length of the string, because we only need to iterate through the string once.

Can the solution be optimized further?

No, this problem is already optimal with a linear scan approach, as both conditions need to be checked during a single traversal.

Are there edge cases to consider for this problem?

Yes, edge cases include strings with very few characters or strings that contain many consecutive 'L's or 'A's.

terminal

Solution

Solution 1

#### Python3

1

2

3

class Solution:
    def checkRecord(self, s: str) -> bool:
        return s.count('A') < 2 and 'LLL' not in s

Continue Practicing

#556 next greater element iii #557 reverse words in a string iii #541 reverse string ii