Test: String Processing - 2 - Software Development MCQ

Which of the following operations can be efficiently performed using a suffix tree?

Which of the following algorithms is used to find all the distinct substrings of a string?

Consider the following Python code snippet:

def longest_palindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    longest_length = 0
    start_index = 0

    for i in range(n):
        dp[i][i] = True
        longest_length = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            if s[i] == s[j]:
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    longest_length = length
                    start_index = i

    return s[start_index: start_index + longest_length]

string = "babad"
print(longest_palindrome(string))
What is the output of the above code?

Consider the following Python code snippet:

def count_distinct_substrings(s):
    n = len(s)
    count = 0
    distinct_substrings = set()

    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if substring not in distinct_substrings:
                count += 1
                distinct_substrings.add(substring)

    return count

string = "banana"
print(count_distinct_substrings(string))
What is the output of the above code?

Consider the following Python code snippet:

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

string1 = "ABCD"
string2 = "ACDF"
print(longest_common_subsequence(string1, string2))
What is the output of the above code?

Consider the following Python code snippet:

def count_subsequences(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[m][n]

string1 = "rabbbit"
string2 = "rabbit"
print(count_subsequences(string1, string2))

What is the output of the above code?

Consider the following Python code snippet:

def count_palindromic_substrings(s):
    n = len(s)
    count = 0

    for i in range(n):
        count += 1  # Counting single characters as palindromic substrings

    dp = [[False] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            if s[i] == s[j]:
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    count += 1

    return count

string = "ababa"
print(count_palindromic_substrings(string))

What is the output of the above code?

Given a string s, find the length of the longest substring without repeating characters. Implement the following function in Python:

def longest_substring_length(s):
    # Your code here

string = "abcabcbb"
print(longest_substring_length(string))

Given two strings s1 and s2, find the length of their longest common substring. Implement the following function in Python:

def longest_common_substring(s1, s2):
    # Your code here

string1 = "ABCD"
string2 = "ACDF"
print(longest_common_substring(string1, string2))

Given a string s, count the number of distinct palindromic substrings. Implement the following function in Python:

def count_distinct_palindromic_substrings(s):
    # Your code here

string = "ababa"
print(count_distinct_palindromic_substrings(string))

Given a string s and a list of words, find the minimum number of spaces to be added to s so that each word in the list is a substring of s. Implement the following function in Python:

def min_spaces(s, words):
    # Your code here

string = "leetcode"
word_list = ["leet", "code"]
print(min_spaces(string, word_list))

Given a string s, find the length of the longest substring that contains at most k distinct characters. Implement the following function in Python:

def longest_substring_k_distinct(s, k):
    # Your code here

string = "eceba"
k = 2
print(longest_substring_k_distinct(string, k))