Student Attendance Record I

Easy

Asked by:

7 views

Topics:

Strings

You are given a string s representing an attendance record for a student 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.

The 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.

Return true if the student is eligible for an attendance award, or false otherwise.

Example 1:

Input: s = "PPALLP"
Output: true
Explanation: The student has fewer than 2 absences and was never late 3 or more consecutive days.

Example 2:

Input: s = "PPALLL"
Output: false
Explanation: 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'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters are allowed in the input string besides 'A', 'L', and 'P'?
What is the maximum length of the input string?
Is the input case-sensitive?
If the input string is empty, should I return true or false?
By 'more than one absence', do you mean strictly greater than one, or one or more?

Brute Force Solution

Approach

The brute force approach to this attendance record problem involves checking every possible attendance record to see if it violates the rules. This means we will generate every combination of 'A', 'L', and 'P' for the given length and validate each one.

Here's how the algorithm would work step-by-step:

Create every possible string of 'A', 'L', and 'P' of the specified length.
For each generated string, check if it contains more than one 'A'.
If it does, that string is invalid and should be discarded.
If it doesn't, check if it contains 'LLL' anywhere in the string.
If it does, that string is also invalid and should be discarded.
If the string passes both checks, then it is a valid attendance record.
Repeat this process until all possible strings have been checked.

Code Implementation

def check_record_brute_force(length_of_record):
    valid_record_count = 0
    possible_characters = ['A', 'L', 'P']

    def generate_attendance_records(current_record, current_length):
        nonlocal valid_record_count

        # Base case: record is long enough
        if current_length == length_of_record:
            absent_count = current_record.count('A')

            # Check for at most one absent
            if absent_count <= 1:

                # Check for no three consecutive late days
                if 'LLL' not in current_record:
                    valid_record_count += 1
            return

        # Recursive generation of strings
        for character in possible_characters:
            generate_attendance_records(current_record + character, current_length + 1)

    generate_attendance_records('', 0)
    return valid_record_count

Big(O) Analysis

Time Complexity

O(3^n * n) – The brute force approach involves generating all possible strings of length n, where each character can be one of three options ('A', 'L', or 'P'). This results in 3^n possible strings. For each of these strings, we need to check for the presence of more than one 'A' and the substring 'LLL'. Checking for 'LLL' and counting 'A's involves iterating through the string, which takes O(n) time. Therefore, the overall time complexity is O(3^n * n).

Space Complexity

O(3^N) – The brute force approach generates every possible string of length N, where N is the length of the attendance record. Since each position in the string can be one of three characters ('A', 'L', 'P'), the total number of possible strings is 3^N. The algorithm needs to store all these generated strings, which takes space proportional to the number of possible strings. Thus, the auxiliary space complexity is O(3^N).

Optimal Solution

Approach

The goal is to determine if a student's attendance record is acceptable based on certain criteria. We need to check for too many absences or consecutive late days by scanning the record once.

Here's how the algorithm would work step-by-step:

Go through the attendance record character by character.
Keep track of the total number of absences.
Also, keep track of the longest streak of consecutive late days.
If the number of absences is two or more, the record is unacceptable.
If there are three or more consecutive late days, the record is also unacceptable.
If neither of those conditions is met after checking the entire record, the record is acceptable.

Code Implementation

def check_record(attendance_record):
    number_of_absences = 0
    consecutive_late_days = 0
    max_consecutive_late_days = 0

    for record in attendance_record:
        if record == 'A':
            number_of_absences += 1

            # More than one absence makes the record invalid.
            if number_of_absences >= 2:
                return False
            consecutive_late_days = 0
        elif record == 'L':
            consecutive_late_days += 1

            # Keep track of the longest streak of consecutive Lates.
            max_consecutive_late_days = max(max_consecutive_late_days, consecutive_late_days)

            # Three or more consecutive lates makes the record invalid.
            if max_consecutive_late_days >= 3:
                return False
        else:
            consecutive_late_days = 0

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the attendance record string once, examining each character to check for absences and consecutive late days. The number of operations performed is directly proportional to the length of the string, which we can denote as n. Therefore, the time complexity is O(n) because we visit each character in the input string a constant number of times.

Space Complexity

O(1) – The algorithm only uses a few integer variables to keep track of the total number of absences and the longest streak of consecutive late days. The amount of memory used by these variables does not depend on the length of the attendance record, which we can denote as N. Therefore, the space complexity is constant and does not scale with the input size, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty input string	Return true if the input is null or empty, as an empty record technically satisfies the criteria of at most one absent and at most two consecutive late days.
String with a single character 'A'	Return false as it has one absent which is allowed, but a single A means the student can attend.
String with a single character 'L'	Return true as it has one late which is within limits
String with a single character 'P'	Return true as it has one present which is within limits
String with two consecutive 'L's	Return true, as it satisfies the criteria.
String with three consecutive 'L's	Return false, as it violates the maximum two consecutive late days rule.
String with two 'A's	Return false, as it violates the maximum one absent day rule.
Very long string with alternating 'P' and 'L'	The solution should iterate through the string only once, ensuring linear time complexity even with very large inputs.

Null or empty input string

How to Handle:

Return true if the input is null or empty, as an empty record technically satisfies the criteria of at most one absent and at most two consecutive late days.

String with a single character 'A'

How to Handle:

Return false as it has one absent which is allowed, but a single A means the student can attend.

String with a single character 'L'

How to Handle:

Return true as it has one late which is within limits

String with a single character 'P'

How to Handle:

Return true as it has one present which is within limits

String with two consecutive 'L's

How to Handle:

Return true, as it satisfies the criteria.

String with three consecutive 'L's

How to Handle:

Return false, as it violates the maximum two consecutive late days rule.

String with two 'A's

How to Handle:

Return false, as it violates the maximum one absent day rule.

Very long string with alternating 'P' and 'L'

How to Handle:

The solution should iterate through the string only once, ensuring linear time complexity even with very large inputs.