Find the Longest Semi-Repetitive Substring

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        ans, i, j, last = 1, 0, 1, 0

        while j < len(s):
            if s[j] == s[j-1]:
                if last:
                    i = last
                last = j
            ans = max(ans, j - i + 1)
            j += 1

        return ans

10 Prerequisite LeetCode Problems

For “2730. Find the Longest Semi-Repetitive Substring”, the following are a good preparation:

“709. To Lower Case” - Helps practice simple string manipulation.
“344. Reverse String” - Further reinforces the basics of string manipulation by reversing a string.
“383. Ransom Note” - Introduces the concept of using one string to construct another.
“3. Longest Substring Without Repeating Characters” - Gives practice on finding unique character sets in strings, similar to finding unique pairs in the main problem.
“125. Valid Palindrome” - Another exercise in string manipulation and checking character properties.
“205. Isomorphic Strings” - Introduces character mapping, which can be a useful concept for the main problem.
“5. Longest Palindromic Substring” - A more complex problem dealing with finding substrings, which is a crucial part of the main problem.
“76. Minimum Window Substring” - This problem is about finding substrings that satisfy certain conditions, similar to the main problem.
“242. Valid Anagram” - Teaches you how to compare characters in two strings, a concept that could be useful in finding semi-repetitive substrings.
“438. Find All Anagrams in a String” - Helps further understand the concept of sliding window to identify substrings in a larger string.

These cover handling substrings, identifying character patterns, and performing string manipulations which are essential to tackle the main problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        res=0
        tab=[1]
        for i in range(1,len(s)):
            if ( s[i]==s[i-1]):
                tab.append(1)
            else:
                tab[-1]=tab[-1]+1
        for j in range(1,len(tab)):
            res=max(res,tab[j]+tab[j-1])

        return max(res,tab[0])

Problem Classification

Language Agnostic Coding Drills

These concepts, when understood individually, can be combined to understand the entire code:

Understanding Data Types (strings, integers): Knowledge about basic data types is the foundation of any programming language. In this code, string and integer data types are used.
List (Array) Initialization: The “tab” variable is initialized as a list with an initial element 1.
Looping through a String: The ‘for’ loop is used to iterate over the string ’s’.
Accessing String Characters by Index: Characters from the string ’s’ are accessed by their index using ’s[i]'.
Comparing Characters: Comparison of the current character with the previous one is performed using the ‘==’ operator.
Appending to a List: New elements are appended to the list using the append() function.
Modifying List Elements: Existing elements of the list are accessed by index and their values are modified.
Accessing Previous Element in List: The concept of accessing the previous element in the list using ‘j-1’ indexing is used.
Finding Maximum: The max() function is used to find the maximum value between two values.
Functions and Methods in Classes: The code is wrapped inside a method of a class, demonstrating object-oriented programming.
Conditional Statements (if-else): Conditional execution of code blocks based on if-else conditions.
Return Statement: The function returns the maximum value calculated.

Here’s the progression of difficulty:

Understanding Data Types (strings, integers)
List (Array) Initialization
Looping through a String
Accessing String Characters by Index
Comparing Characters
Appending to a List
Modifying List Elements
Accessing Previous Element in List
Conditional Statements (if-else)
Finding Maximum
Functions and Methods in Classes
Return Statement

Targeted Drills in Python

Here are some coding drills corresponding to each learning concept:

Understanding Data Types (strings, integers)

1
2
3
4
5
6
7
# Declare a string variable and an integer variable
string_var = "Hello, world!"
integer_var = 1234

# Print their values
print(string_var)
print(integer_var)

List (Array) Initialization

1
2
3
# Initialize a list with an integer
integer_list = [1]
print(integer_list)

Looping through a String

1
2
3
# Loop through a string and print each character
for char in "Hello, world!":
    print(char)

Accessing String Characters by Index

1
2
# Access and print the 5th character of a string
print("Hello, world!"[4])

Comparing Characters

1
2
3
# Compare two characters
print('a' == 'b')
print('c' == 'c')

Appending to a List

1
2
3
# Append an integer to a list
integer_list.append(2)
print(integer_list)

Modifying List Elements

1
2
3
# Modify the first element of the list
integer_list[0] = 5
print(integer_list)

Accessing Previous Element in List

1
2
# Access and print the last element of a list
print(integer_list[-1])

Conditional Statements (if-else)

1
2
3
4
5
# If-else statement
if 'a' == 'b':
    print("Equal")
else:
    print("Not equal")

Finding Maximum

1
2
# Find the maximum of two numbers
print(max(10, 20))

Functions and Methods in Classes

1
2
3
4
5
6
7
8
# Define a simple class with a method
class MyClass:
    def print_hello(self):
        print("Hello, world!")

# Create an object and call the method
obj = MyClass()
obj.print_hello()

Return Statement

1
2
3
4
5
6
# Define a function that returns a value
def square(num):
    return num ** 2

# Call the function and print the result
print(square(5))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        res = 0
        tab = [1]
        for i in range(1, len(s)):
            if (s[i] == s[i-1]):
                tab.append(1)
            else:
                tab[-1] = tab[-1] + 1
        for j in range(1,len(tab)):
            res = max(res, tab[j] + tab[j-1])

        return max(res,tab[0])

Problem Classification

This problem is primarily a string manipulation and dynamic programming problem within the realm of computer science and algorithm design.

The ‘What’ components are:

A string ’s’ of digits from 0 to 9.
A definition of semi-repetitive string which allows at most one consecutive pair of the same digits.
The task to find the length of the longest semi-repetitive substring in ’s’.

Classifying the problem:

Domain: This is a problem of string manipulation and dynamic programming in computer science. String manipulation is needed to identify the substrings, and dynamic programming is typically employed to optimize the process of finding the longest such substring.
Deterministic or stochastic: The problem is deterministic as there’s no random or probabilistic element involved. The input and constraints are clearly defined and the output is a deterministic function of the input.
Static or dynamic: The problem is static as we’re given the entire input (the string ’s’) upfront and it doesn’t change over the course of the problem.
Discrete or continuous: The problem is discrete since we’re dealing with strings of digits which are discrete entities.
Single or multi-objective: This problem is single-objective. The single objective is to find the length of the longest semi-repetitive substring in ’s’.
Well-structured or ill-structured: The problem is well-structured as it has a clear goal, the information provided is complete and the problem can be solved by applying known algorithmic methods.

Language Agnostic Coding Drills

Dissection of the code into distinct concepts:

a. Concept 1 - Iteration: Iterating over elements of an array or string using a for loop. This concept is foundational for most algorithms.

b. Concept 2 - Indexing and accessing elements: Accessing and manipulating elements in a list using their indices. This is a very basic concept used for manipulating arrays or lists.

c. Concept 3 - Conditional statements: Using if-else statements for conditional execution of code based on certain criteria. This is a fundamental control flow concept.

d. Concept 4 - List manipulation: Appending elements to a list and updating list elements. This concept is important for many problems involving collection and manipulation of data.

e. Concept 5 - Use of max function: Using the max function to keep track of the maximum value seen so far. This concept is often used in optimization problems.

List of concepts in order of increasing difficulty with a brief description:

a. Iteration: Looping through each character in a string. This is a foundational concept in most programming languages and is generally one of the first things learned when learning to code. Difficulty: 1/5.

b. Indexing and accessing elements: Accessing specific elements of a list or string by their indices. This is a fundamental operation for any kind of array manipulation or access. Difficulty: 2/5.

c. Conditional statements: Using if-else statements to conditionally execute different parts of the code. This is a basic control flow mechanism and is used almost universally in coding. Difficulty: 2/5.

d. List manipulation: Creating and modifying lists, including appending elements and modifying existing elements. This is slightly more advanced as it involves the manipulation of data structures. Difficulty: 3/5.

e. Use of max function: Using the max function to maintain the maximum value seen so far. This is a slightly more advanced concept as it involves the use of an inbuilt function in an optimization context. Difficulty: 3/5.

Problem-solving approach:

The solution to the problem involves using a dynamic programming approach where we keep track of the length of semi-repetitive substrings. The idea is to iterate over the string and track the length of semi-repetitive substrings in a list (tab). If the current character is the same as the previous one, a new substring starts, and 1 is appended to the list. Otherwise, the length of the current substring (tab[-1]) is incremented. Finally, we iterate over the list tab and maintain the maximum length of the semi-repetitive substring (which can include at most one consecutive pair of the same digits). This length is returned as the result.

The identified coding concepts contribute to this solution as follows:

Iteration: We need to iterate over the string to check each character and over the list tab to find the maximum length of a semi-repetitive substring.
Indexing and accessing elements: We need to access the characters of the string and the elements of the list tab by their indices to perform various operations.
Conditional statements: We need to use if-else statements to differentiate between when the current character is the same as the previous one and when it is different.
List manipulation: We need to append to and modify the elements of the list tab to keep track of the lengths of semi-repetitive substrings.
Use of max function: We use the max function to maintain the maximum length of a semi-repetitive substring found so far.

Targeted Drills in Python

Python drills for each concept:

Concept 1 - Iteration:
1 2
for i in range(10): print(i)

Concept 2 - Indexing and accessing elements:

1
2
3
4
arr = [1, 2, 3, 4, 5]
print(arr[2])  # accessing the element at index 2
arr[2] = 10  # modifying the element at index 2
print(arr)

Concept 3 - Conditional statements:

1
2
3
4
5
x = 10
if x > 5:
    print("x is greater than 5")
else:
    print("x is not greater than 5")

Concept 4 - List manipulation:

1
2
3
4
5
arr = [1, 2, 3]
arr.append(4)  # appending 4 to the list
print(arr)
arr[1] = 10  # modifying the element at index 1
print(arr)

Concept 5 - Use of max function:

1
2
3
arr = [1, 2, 3, 4, 5]
max_val = max(arr)
print(max_val)  # prints 5

Drills for specific needs of the problem:

Drill 1 - Creating and manipulating a list of lengths of semi-repetitive substrings:

1
2
3
4
5
6
7
8
s = '112233'
tab = [1]
for i in range(1, len(s)):
    if s[i] == s[i - 1]:
        tab.append(1)
    else:
        tab[-1] += 1
print(tab)  # prints [2, 2, 2]

Drill 2 - Finding the maximum length of a semi-repetitive substring:

1
2
3
4
5
tab = [2, 2, 2]
max_len = 0
for i in range(1, len(tab)):
    max_len = max(max_len, tab[i] + tab[i - 1])
print(max_len)  # prints 4

How to merge these drills for the final solution:

The final solution would involve merging these drills in a way that implements the problem-solving approach described in the previous response. We would first iterate over the string s to create the list tab of lengths of semi-repetitive substrings. Then, we would iterate over this list to find and return the maximum length of a semi-repetitive substring. All these operations would involve using the other concepts (indexing and accessing elements, conditional statements, list manipulation, and the use of the max function) as needed.