# Algorithm to print the Minimum number of adjacent character swaps necessary to remove all instances of "VK" in a given string?

For example, how many adjacent swaps are at least needed to convert some string such as BVVKCV to one without any instances of VK?

Input-length of the string will be within the range 1 <= length <= 200.
VK will be hardcoded across all test cases.

Input string examples:

Input:  VKVKVVVKVOVKVQKKKVVK
Output: 8

Input:  VVKEVKK
Output: 3

Input:  JUSTIN
Output: 0

• I've formatted your post a bit. As mentioned by @JoKing above, is the "vk" hard-coded, or given as second input? Also, you will need a winning criteria tag. [code-golf] is the most common one to use. Dec 6, 2018 at 9:50
• The "VK" is hard coded. Dec 6, 2018 at 9:54
• Lowercase vk or uppercase? Also, I'd recommend rewriting the title to something less "I need help with my homework" sounding
– Jo King
Dec 6, 2018 at 10:55
• I would appreciate some more test cases =D Dec 6, 2018 at 19:04
• Suggested test case: KV => 0 Dec 10, 2018 at 17:38

# Japt, 44 bytes

m£Z¯Y cZtY2 Ô cZsY+2Ãrc
®¬ø"VK"
W+VÌ
Ve ?ß:W


Try it online!

It times out on the first test case because it's super inefficient (something like O(n^n)?) but it should be a viable algorithm. Input is weird; it is a singleton list containing the input, but the input itself is formatted as a list of upper-case characters. I think that would typically be valid, but if not let me know.

Explanation:

#Step 1: try all the swaps
m                          #For each string Z reachable with n swaps (n starts at 0)
£                  Ã      # For each letter Y in Z:
Z¯Y                      #  Get the letters before it in Z
c                    #  Concat
ZtY2 Ô              #  Y swapped with the following character
c            #  Concat
ZsY+2       #  The rest of Z
rc    #Flatten by one level
#Result: A list of all strings reachable with n+1 swaps

#Step 2: Check for "VK"
®¬         #For each string from Step 1:
ø"VK"    # Check whether it contains "VK"
#Result: A list where 1 indicates there was "VK" and 0 otherwise

#Step 3: Increment the counter appropriately
W+      #Increase the counter by
VÌ    #The value for the original string when run through step 2
#Result: 0 if 0 swaps were required, the current number of swaps otherwise

#Step 4: Iterate or end
Ve ?       #If all the reachable strings contain "VK"
ß      # Repeat the program with the current values
:W    #Otherwise return the counter
#Result: Outputs the counter when a non-"VK" string is found.

• A couple of quick savings to get you down to 44 bytes. Dec 11, 2018 at 9:41

# Python 3, 125 bytes

s={input()}
a=0
while all("VK"in q for q in s):a+=1;s={a[:i]+a[i+1]+a[i]+a[i+2:]for a in s for i in range(len(a)-1)}
print(a)


Try it online!

Basic BFS.