mono_lith's blog

By mono_lith, history, 2 years ago, In English

recently we had a coding test in our college the question was you are given a string S and a vector of triplets which contains three things a,b,c where you can replace a character with b character at the cost of c(integer value rest a,b are character) you have to find the minimum total cost to make the string S have a palindromic substring of size >=2

s.size<=10^5

vector.size<=10^5

if you are unable to make a palindromic substring print -1 ;

eg

abcab

2

a b 3

b a 4

output -> 3

my approach ->

was to make a directed weighted graph from the given triplet vector and the we will only have 2 or 3 size palindromic substring so i brutefoce on that and for each pair of character (i,j) do a dfs on the graph and store the values in a dp still getting wa

i think this type of question i have seen on codeforces some D or E problem but I am unable to find that problem

please if anyone could help in this problem also the coding test is over so not doing this for cheating just curious about the mistake after investing so much time to solve it.

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?