551. Student Attendance Record I

EasyString
Leetcode Link

Problem Description

In this problem, we receive a string s representing a student's attendance record. Each character in this record signifies whether the student was Absent ('A'), Late ('L'), or Present ('P') on a given day. The goal is to determine whether the student qualifies for an attendance award based on this record. The criteria for qualification are simple:

  • First, the student must have been absent ('A') for strictly fewer than 2 days in total.
  • Second, the student must never have been late ('L') for 3 or more consecutive days.

The function must return true if the student meets both criteria for the attendance award, otherwise, it should return false.

Intuition

The intuition behind the provided solution is straightforward. Since the criteria are not compound and don't require advanced checks, we can use two simple checks directly on the string:

  1. Counting the number of 'A's: We ensure that the count of absences is less than 2, which means either 0 or 1 absence is acceptable.
  2. Checking for 'LLL': To verify the student was never late for 3 or more consecutive days, we look for the substring 'LLL' in s. If it's not found, the student has never been late for 3 consecutive days.

The solution leverages the inbuilt count method to count the absences and the in operator to check for the presence of three consecutive 'L's. Since the problem statement requires both conditions to be true, we use the logical AND operator (and) to combine the two conditions. If both conditions evaluate to true, the overall expression returns true, indicating the student is eligible for the award.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Solution Approach

The implementation of the solution is straightforward and utilizes two built-in Python features, which are simple to understand and do not require additional data structures or complex algorithms:

  1. .count() Method: This is a built-in string method in Python that counts the number of times a substring appears in the string. In our solution, s.count('A') is used to count the number of 'A's, which represent absences in the attendance record. We check that this count is less than 2.

  2. Substring Checking With in Operator: We use the in keyword to check if a substring appears within a larger string. In this case, we're checking if 'LLL' (representing three consecutive late days) is a substring of s. If 'LLL' is not found, it means the student has not been late for 3 or more consecutive days.

By combining these two checks with the logical AND operator (and), the solution checks both conditions stipulated in the problem description. Specifically, the code snippet s.count('A') < 2 and 'LLL' not in s will evaluate to true only if both conditions are met:

  • There are fewer than 2 absences, which means the s.count('A') < 2 condition is true.
  • There are no instances of 3 consecutive lates, which means the 'LLL' not in s condition is true.

The function checkRecord hence returns a single boolean value, which directly answers whether the student is eligible for the attendance award according to the given rules. The efficiency of this approach lies in the fact that both checks are performed in constant time—there's no loop or iteration across the string, making the time complexity O(n) where n is the length of the string, with the space complexity being O(1) as no extra space is used.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Let's consider the string s = "PPALLP" as a student's attendance record for illustration purposes.

  1. Counting Absences: We apply s.count('A') to count how many times 'A' appears in s. For our example, s.count('A') will return 1 since there is only one 'A' character in the string PPALLP.

  2. Checking for Three Consecutive 'L's: We then check if the substring 'LLL' exists in s by using the in operator: 'LLL' not in s. For our example, 'LLL' does not appear in PPALLP. Therefore, 'LLL' not in s would be true.

Now we apply the logical AND operator to combine these two checks:

  • Since s.count('A') < 2 evaluates to true (1 < 2 is true),
  • and 'LLL' not in s evaluates to true,

the combined condition is true AND true, which yields true. Therefore, the function checkRecord("PPALLP") would return true, indicating that the student qualifies for an attendance award based on the given record.

Solution Implementation

1class Solution:
2    def checkRecord(self, s: str) -> bool:
3        """
4        Check if a student's attendance record is eligible for an award.
5        The record is eligible if it contains:
6        - Less than two 'A' (Absent) records.
7        - No more than two continuous 'L' (Late) records.
8      
9        :param s: A string representing the student's attendance record.
10        :type s: str
11        :return: True if the record is eligible, False otherwise.
12        :rtype: bool
13        """
14
15        # Check for less than two Absents
16        less_than_two_absents = s.count('A') < 2
17
18        # Check for not having three continuous Lates
19        no_three_continuous_lates = 'LLL' not in s
20
21        # Return True if both conditions are met, otherwise False
22        return less_than_two_absents and no_three_continuous_lates
23
24# Example usage:
25# creating an instance of Solution class
26solution = Solution()
27# invoking the checkRecord method with a sample record string
28eligible = solution.checkRecord("PPALLP")  # This should return True
29
1class Solution {
2    // This method checks if a student's attendance record is eligible for an award.
3    // The record is eligible if it contains at most one 'A' (absence)
4    // and it does not contain a 'LLL' (late three times in a row).
5    public boolean checkRecord(String attendanceRecord) {
6        // Check that there is at most one 'A' in the string by confirming that
7        // the first index of 'A' is the same as the last index of 'A'.
8        boolean hasAtMostOneAbsence = attendanceRecord.indexOf("A") == attendanceRecord.lastIndexOf("A");
9      
10        // Check that 'LLL' does not appear in the string.
11        boolean noThreeConsecutiveLates = !attendanceRecord.contains("LLL");
12      
13        // The student is eligible for an award if both conditions are true.
14        return hasAtMostOneAbsence && noThreeConsecutiveLates;
15    }
16}
17
1class Solution {
2public:
3    // This method checks if the student's record is eligible for an award.
4    // A record is eligible if it contains fewer than two 'A's (absences)
5    // and does not contain three consecutive 'L's (lates).
6    bool checkRecord(string record) {
7        // Check for the number of absences
8        // The record is ineligible if 'A's appear 2 or more times
9        bool isAbsenceLessThanTwo = count(record.begin(), record.end(), 'A') < 2;
10      
11        // Check for consecutive lates
12        // The record is ineligible if 'LLL' is found
13        bool hasNoConsecutiveLates = record.find("LLL") == string::npos;
14      
15        // The record is eligible only if both conditions are satisfied
16        return isAbsenceLessThanTwo && hasNoConsecutiveLates;
17    }
18};
19
1// Function to determine if a student's attendance record is eligible
2// The record is considered eligible if it contains at most one 'A' (absence)
3// and does not contain three consecutive 'L' (late).
4function checkRecord(attendanceRecord: string): boolean {
5    // Check if the record contains at most one 'A' by comparing the first and last occurrence.
6    // If they are the same, there is either one or zero 'A' in the record.
7    const isSingleAbsenceOrLess = attendanceRecord.indexOf('A') === attendanceRecord.lastIndexOf('A');
8
9    // Check if the record does not contain 'LLL'.
10    const doesNotContainThreeLates = attendanceRecord.indexOf('LLL') === -1;
11
12    // Return true if both conditions are met, otherwise return false.
13    return isSingleAbsenceOrLess && doesNotContainThreeLates;
14}
15
Not Sure What to Study? Take the 2-min Quiz：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Time and Space Complexity

The time complexity of the provided function is O(n), where n is the length of the string s. This is because both count and in methods must potentially examine each character in the string – count to tally occurrences of 'A' and the in operation to check for the substring 'LLL'.

The space complexity of the function is O(1) because no additional space is used that is dependent on the input size; the storage used is constant, related only to the single boolean result and fixed string checks, and does not grow with the size of s.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫