Problem 551

Abstract / Summary

A student can be absent at most once and cannot be late for more than two consecutive days in a record of up to 30 days.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0551.py

class Solution:
    def checkRecord(self, s: str) -> bool:
        # let's do it the very tricky way ...
        return s.find("LLL") == s.find("A", 1 + s.find("A"))
4 lines | 170 bytes | submitted August 22, 2023 | GitHub   33% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 49% (400k+ submissions).

Typical patterns to solve this problem:
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a single method checkRecord that determines whether a given attendance string satisfies two constraints: it must contain no more than one occurrence of the character 'A' and it must not contain the substring 'LLL'. The logic is expressed in a single return statement that leverages Python’s built-in str.find method.

Core Logic

The method consists of two primary operations, each performed by a call to find.

The first operation searches for three consecutive late marks:

s.find("LLL")

If the substring 'LLL' is present, find returns the index of its first character; otherwise it returns -1.

The second operation looks for a second occurrence of an absent mark:

s.find("A", 1 + s.find("A"))

The inner find("A") locates the first 'A'. Adding one to that index creates a start position that skips the first 'A'. The outer find then searches from that position for another 'A'. If a second 'A' exists, the call returns its index; if not, it returns -1.

The method returns the Boolean result of comparing these two indices:

return s.find("LLL") == s.find("A", 1 + s.find("A"))

Equality holds only when both calls yield -1, meaning the string contains neither 'LLL' nor a second 'A'. In every other situation the indices differ, causing the method to return False.

Edge Cases Handled

When the input string is empty, both find calls return -1, and the method correctly returns True.

If the string contains a single 'A' but no 'LLL', the inner find("A") returns a non-negative index, the outer find starts after that position and fails to locate another 'A', returning -1. Since the 'LLL' search also returns -1, the method returns True.

When the string includes two or more 'A' characters, the outer find discovers the second 'A' and returns its index (a non-negative value). Because the 'LLL' search still yields -1 (unless 'LLL' is also present), the comparison is false and the method returns False.

If the string contains the substring 'LLL' at any position, the first find returns a non-negative index. Even if there is no second 'A', the second find returns -1, making the comparison false. Thus any occurrence of three consecutive 'L' characters leads to a False result.

The implementation also gracefully handles strings that contain both a second 'A' and 'LLL'. In that case both find calls return non-negative indices that are unlikely to be equal, so the method returns False.

Performance Characteristics

The solution relies exclusively on the highly optimized C implementation of str.find. Each call scans the string at most once, and the two scans are independent. By avoiding explicit Python loops or additional data structures, the method minimizes overhead and benefits from the interpreter’s internal optimizations for substring search. The use of a single return expression eliminates the need for temporary variables, reducing memory footprint during execution.

Overall, the approach achieves the required validation with minimal computational work, leveraging built-in string operations to deliver fast and concise evaluation.

written by openai gpt

ELI5 - Simplified Explanation

Imagine this code is like a little robot helper that looks at a list of attendance marks for a student. The marks are stored in a string, which is just a fancy way of saying a row of letters. The robot is checking two specific rules to see if the student gets an award.

First, the robot looks for three letters in a row that say L. This stands for being late. If the robot finds those three Ls tucked together anywhere in the row, it knows the student missed too many school days in a row.

Second, the robot counts how many times the letter A appears. This stands for being absent. If the letter A shows up more than one single time, the student has been away too much.

The code works by using clever tricks to see if the Ls are grouped together and if there is more than one A. It looks at the row of letters to decide if the student followed the rules or if they broke them. If the student stays out of trouble by not being late three times in a row and by not being absent more than once, the code confirms everything is okay.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 3 | μ = 3.77 | σ = 1.89

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Python Go TS
LeetcodeHelp C++ Java Python
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
gouthampradhan Java
halfrost Go
JoshCrozier JS
keineahnung2345 C++
linouk23 C++
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
varunu28 Java
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
gouthampradhan Java
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
linouk23 C++
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
varunu28 Java
zfang399 C++
35 links | 22 authors | 10 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

2 easy 6 medium
9 solutions   August 22, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality