String Reductions – HackerRank Solution

In this post, we will solve String Reductions HackerRank Solution. This problem (String Reductions) is a part of HackerRank Functional Programming series.

Task

Given a string, str = s₁, s₂, . . . , s_n, consisting of n lowercase English characters (a – z), remove all of the characters that occurred previously in the string. Formally, remove all characters, s_i, for:

 j, s_j = s_i and j < i

Input Format

A single line of input containing a string str of length n.

Constraints

• 1 <= n <= 10⁵
• s_i = {a, b, . . . , z}, where 1 <= i <= n

Output Format

Print the string after removing all the characters that occurred previously.

Sample Input #00

accabb

Sample Output #00

acb

Sample Input #01

abc

Sample Output #01

abc

Sample Output #02

pprrqq

Sample Output #02

prq

Explanation

Test case #00: For str = “accabb“, characters at indexes 3, 4, 6 are removed as they have already occurred.
Test case #01: As each character occurs only once, nothing is removed.
Test case #02: For str = “pprrqq“, each character occurs twice. The second of these characters is removed. Characters at positions 2, 4 and 6 are removed.

Solution – String Reductions – HackerRank Solution

Scala

import java.util.Scanner

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val s = sc.nextLine

    sc.close()

    def solve(s: String): String = {
      @scala.annotation.tailrec
      def inner(s: List[Char], used: Set[Char], acc: List[Char]): String = s match {
        case Nil => acc.reverse.mkString("")
        case c :: cs => if (used.contains(c)) inner(cs, used, acc) else inner(cs, used + c, c :: acc)
      }

      inner(s.toList, Set(), Nil)
    }

    println(solve(s))
  }
}

Note: This problem (String Reductions) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.