551. Student Attendance Record I
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 46.1%
Problem Breakdown
The problem requires determining whether a student is eligible for an attendance award based on their attendance record. The record is given as a string s where each character can be 'A' (Absent), 'L' (Late), or 'P' (Present). The student is eligible if they meet the following criteria:
- They were absent (
'A') for fewer than 2 days. - They were never late (
'L') for 3 or more consecutive days.
Inputs:
- A string
srepresenting the attendance record.
Outputs:
- A boolean value indicating whether the student is eligible for the award (
trueorfalse).
Implicit Constraints/Edge Cases:
- The length of
sis between 1 and 1000 characters. - The string only contains
'A','L', or'P'. - Edge cases include strings with no absences, all presences, or various combinations of
'A'and'L'.
Intuition
The brute-force approach would involve iterating through the string multiple times to count the number of 'A's and check for sequences of three consecutive 'L's. This approach is inefficient with a time complexity of O(n^2) due to nested loops.
A more efficient approach involves making a single pass through the string while keeping track of the counts of 'A's and checking for sequences of three consecutive 'L's. This reduces the time complexity to O(n).
Approach
- Initialize two variables:
absent_countto count the number of'A's and a flagconsecutive_lateto check for three consecutive'L's. - Iterate through each character in the string:
- If the character is
'A', incrementabsent_count. - If the character is
'L', check if it’s part of a sequence of three consecutive'L's by checking the previous two characters.
- If the character is
- After iterating through the string, check if
absent_countis less than 2 andconsecutive_lateis not set totrue. - Return
trueif both conditions are met; otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string
s. We make a single pass through the string. - Space Complexity: O(1). We use a constant amount of extra space for variables.
Solution
def checkRecord(s: str) -> bool:
absent_count = 0
consecutive_late = False
for i in range(len(s)):
if s[i] == 'A':
absent_count += 1
if absent_count >= 2:
return False
elif s[i] == 'L':
if i >= 2 and s[i-1] == 'L' and s[i-2] == 'L':
consecutive_late = True
break
return not consecutive_late
# Example usage:
# print(checkRecord("PPALLP")) # Output: true
# print(checkRecord("PPALLL")) # Output: false
Edge Cases Handled
- No absences (
"PPPLLP"): The function correctly returnstrueas there are fewer than 2 absences and no three consecutive lates. - All presences (
"PPPPPP"): The function correctly returnstrueas there are fewer than 2 absences and no three consecutive lates. - Single absence (
"PPLLLA"): The function correctly returnsfalsebecause of the three consecutive lates. - Multiple absences (
"AAPLAL"): The function correctly returnsfalsebecause there are two absences.
The solution is correct, efficient, and clear. It handles all edge cases as described in the problem statement.