Algorithm No Repeats Please in Swift

Hello ladies and gentlemen, Leo here. Today we’ll continue the series Algorithms, the Final Frontier. Always remember, this is ONE of many possible solutions for the problem. The challenge today involves permutation and it algorithm is called No repeats Please a legendary Leetcode challenge.

Algorithms are a very important part of our day-to-day job and it is very important to always practice to be up to date in your skills.

The challenge is here: Link to Challenge

The Problem

Let’s go!

The problem: Return the number of total permutations of the provided string that don’t have repeated consecutive letters. Assume that all characters in the provided string are each unique. For example, aab should return 2 because it has 6 total permutations (aab, aab, aba, aba, baa, baa), but only 2 of them (aba and aba) don’t have the same letter (in this case a) repeating.

Solving Algorithm No Repeats Please Challenge

Let’s start with this solution:

var input = "aab"
var charArray = Array(input)
var result : [String] = []

func wirthPermutation(_ charArray: [Character], _ n: Int) {
    if n == 0 {
        let actualPermutation = String(charArray)
        if actualPermutation.range(of: #"([\w])\1"#, options: .regularExpression) == nil {            
            result.append(actualPermutation)
        }
    } else {
        var b = charArray
        wirthPermutation(b, n - 1)
        for i in 0..<n {
            b.swapAt(i, n)
            wirthPermutation(b, n - 1)
            b.swapAt(i, n)
        }
    }
}

wirthPermutation(charArray, charArray.count-1) //  have to call it with array count minus one
print(result)

We here are using a recursive algorithm to find all permutations. When the n comes to zero it means that we can append that permutation to the final result, this is our escape clause

Permutation problems are hard, so take your time to study that and ask me if you need any help with them! Don’t struggle alone, it is always better to have someone that you can ask for help.

Continue Algorithm Studying

A very common algorithm strategy is using breadth-first search (BFS) and depth-first search (DFS) to solve problems. If you have any doubts about how to implement those algorithms with ultimate simplicity this article is for you. There you will find templates for BF

Using memorization to enable dynamic programming is a great strategy for your algorithms, this way you can learn how to find the longest increasing subsequence in Swift. There we will use an auxiliary structure to keep the current count while we traverse the array just one time.

Summary

You should be asking yourself “Why Wirth permutation?” because the inventor of this recursive algorithm is Nikalus Wirth the legendary Swiss computer scientist.

That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or just leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.

Thanks for the reading and… That’s all folks.

Image Credit: Wikiart