Find the substring and its length which is in alphabetical order

Sudarshan Kasar

·

Follow

1 min read

·

Feb 21, 2024

Listen

Share

Given String s of size n
 Perform below operation to get the result
 if(s(i-1) > s(i)) then delete s(i)

 Find the highest substring which is in alphabetical order,
 And the minimum number of operation required to sort the string

 Note - All the charecters are on lower case

 eg. s="ecddgcfkhek" , then the o/p substring is "egkk" operations - 7

package playground

object SubStringInAlphabeticalOrder extends App {
  /**
   * Given String s of size n
   * Perform below operation to get the result
   * if(s(i-1) > s(i)) then delete s(i)
   *
   * Find the highest substring which is in alphabetical order,
   * And the minimum number of operation required to sort the string
   *
   * Note - All the charecters are on lower case
   *
   * eg. s="ecddgcfkhek" , then the o/p substring is "egkk" operations - 7
   * */

  val s = "ecddgcfkhek"

  case class A (var s: String, var i: Int)

  val result: A = s.toSeq.foldLeft(A(s"", 0))((res, currentChar) => {
    if (res.s.size > 0) {
      if (res.s.charAt(res.s.length - 1).hashCode > currentChar.hashCode) {
        A(res.s, res.i + 1)
        //A(s"$res", res.i + 1)
      } else A(s"${res.s}$currentChar", res.i)
    } else A(s"${res.s}$currentChar", res.i)
  }
  )

  println(result)
}