Finding Substring Occurrences in Kotlin | CodeSignal Learn

Finding Substring Occurrences in Kotlin | CodeSignal Learn

Introduction

Hello, and welcome to our analysis lesson. In this lesson, we will tackle a common problem in the field of string manipulations . We will learn how to find all occurrences of a substring within a larger string . The techniques you will master today can be utilized in numerous situations, such as text processing and data analysis. Are you ready to get started? Let's jump right in!

Task Statement and Description

Here is this unit's task: We have two lists of strings, both of identical lengths — the first containing the "original" strings and the second containing the substrings . Our goal is to detect all occurrences of each substring within its corresponding original string and, finally, return a list that contains the starting indices of these occurrences. Remember, the index counting should start from 0. Example Let's consider the following lists: Original List: { "HelloWorld", "LearningKotlin", "GoForBroke", "BackToBasics" } Substring List: { "loW", "ear", "o", "Ba" } . The following are the expected outputs: In "HelloWorld", "loW" starts at index 3. In "LearningKotlin", "ear" starts at index 1. In "GoForBroke", "o" appears at indices 1, 3, and 7. In "BackToBasics", "Ba" starts at indices 0 and 6. Thus, when findSubString(listOf("HelloWorld", "LearningKotlin", "GoForBroke", "BackToBasics"), listOf("loW", "ear", "o", "Ba")) is invoked, the function should return: {"The substring 'loW' was found in the original string 'HelloWorld' at position(s) 3.", "The substring 'ear' was found in the original string 'LearningKotlin' at position(s) 1.", "The substring 'o' was found in the original string 'GoForBroke' at position(s) 1, 3, 7.", "The substring 'Ba' was found in the original string 'BackToBasics' at position(s) 0, 6."} Although this task may seem fairly straightforward, it can prove challenging. However, don't worry! We will break it down step by step.

Step-by-Step Solution: Step 1, Creating the Output List

Initially, we need to create a space to store our results. Can you think of a Kotlin data type that would be ideal for this task? That's right! A MutableList would be perfect! Kotlin fun findSubString(origStrs: List<String>, substrs: List<String>): List<String> {val result = mutableListOf<String>()

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Step 2: Pairing Strings and Locating First Occurrence

To pair original strings with their substrings, we use a simple loop. In our case, both lists share the same length, so we can use their indices to pair them correctly. To find the first occurrence of each substring in the corresponding original string, we utilize the indexOf method: for (i in origStrs.indices) {var startPos = origStrs[i].indexOf(substrs[i]) In string.indexOf(substr), we provide the substring that we intend to locate. The function starts its search from the beginning because we have not specified a starting position.

Step 3: Locating Subsequent Occurrences

The next step is to find the subsequent instances of the substring in the original . To do this, we will use a while loop. But when should we stop looking for more occurrences? When our indexOf function returns -1, it indicates there are no more matches to be found. Each time we locate a match, we record its starting index in the matchIndices list, adjust the startPos, and begin the search anew: val matchIndices = mutableListOf<Int>() while (startPos != -1) {matchIndices.add(startPos) startPos = origStrs[i].indexOf(substrs[i], startPos + substrs[i].length)}

Kotlin

        val matchIndices = mutableListOf<Int>()
        while (startPos != -1) {
            matchIndices.add(startPos)
            startPos = origStrs[i].indexOf(substrs[i], startPos + substrs[i].length)
        }

Finally, we format the result for improved readability and add it to the result list using Kotlin's string templates:

Kotlin

        if (matchIndices.isNotEmpty()) {
            val formattedResult = "The substring '${substrs[i]}' was found in the original string '${origStrs[i]}' at position(s) ${matchIndices.joinToString(", ")}."
            result.add(formattedResult)
        }
    }
    return result
}

Here is the complete function, incorporating all the steps we have discussed so far:

Kotlin

fun findSubString(origStrs: List<String>, substrs: List<String>): List<String> {
    val result = mutableListOf<String>()

    for (i in origStrs.indices) {
        var startPos = origStrs[i].indexOf(substrs[i])
        val matchIndices = mutableListOf<Int>()

        while (startPos != -1) {
            matchIndices.add(startPos)
            startPos = origStrs[i].indexOf(substrs[i], startPos + substrs[i].length)
        }

        if (matchIndices.isNotEmpty()) {
            val formattedResult = "The substring '${substrs[i]}' was found in the original string '${origStrs[i]}' at position(s) ${matchIndices.joinToString(", ")}."
            result.add(formattedResult)
        }
    }
    return result
}

fun main() {
    // Call the function
    val result = findSubString(
        listOf("HelloWorld", "LearningKotlin", "GoForBroke", "BackToBasics"),
        listOf("loW", "ear", "o", "Ba")
    )
    for (res in result) {
        println(res)
    }
}