Question

Michelle has created a word game for her students. the word game begins with michelle writing a string and a number, k, on the board. the students must find a substring of size k such that there is exactly one character that is repeated one; in other words, there should be k - 1 distinct characters in the substring.

Answer 1

This question is incomplete. However, a possible algorithm to find a solution would be:

let String be the string written by the teacher
let k be the size of the substrings
let L be a set of substrings of length k
let M be a set of substrings of length k with k-1 distinct characters
let temp be a temporary string
while String >= k {
let temp be the first four characters of String
add temp to L
delete the first character of String
}
For each substring in L{
int distinct_characters = 4
for int i = 1 to 3 {
char t = ith character of substring
for int j = i to 4{
if jth character of substring = t then{
distinct_characters = distinct_characters - 1
}
}
}
if distinct_characters = 3 then{
add substring to M
}
}