-
Notifications
You must be signed in to change notification settings - Fork 0
/
minMovesToMakePalindrome.js
76 lines (65 loc) · 1.73 KB
/
minMovesToMakePalindrome.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
const reverse = (s) => s.split("").reverse().join("");
const isPalindrome = (s) => reverse(s) === s;
const swap = (chars, a, b) => {
let temp = chars[a];
chars[a] = chars[b];
chars[b] = temp;
};
const getMinNumberOfSwaps = (chars) => {
let numberOfSwaps = 0;
let tryInverse = false;
while (true) {
let [left, right] = [0, chars.length - 1];
let leftChar = chars[left];
let rightChar = chars[right];
if (leftChar === rightChar) break;
// findNearest(s, left, right);
// const condition = tryInvers
while (left < right) {
leftChar = chars[left];
rightChar = chars[right];
if (leftChar !== rightChar) {
if (tryInverse) right--;
else left++;
} else {
if (tryInverse) {
swap(chars, right, right + 1);
} else {
swap(chars, left, left - 1);
}
numberOfSwaps++;
break;
}
}
if (left === right) {
// reset
tryInverse = true;
}
}
return numberOfSwaps;
};
/**
* @param {string} s
* @return {number}
*/
var minMovesToMakePalindrome = function (s) {
let ans = 0;
let [left, right] = [0, s.length - 1];
let orginal = s.split("");
chars = orginal;
while (left < right) {
ans += getMinNumberOfSwaps(chars);
left++;
right--;
chars = orginal.slice(left, right + 1);
}
if (isPalindrome(orginal.join(""))) return ans;
console.log(orginal);
};
("csaaqtqe");
("qcsaateq");
// console.log(getMinNumberOfSwaps("qvvtsaaqtqesvvqc".split("")));
// console.log(getMinNumberOfSwaps("eqvvhtcsaaqtqesvvqch".split("")));
console.log(minMovesToMakePalindrome("eqvvhtcsaaqtqesvvqch"));
// console.log(minMovesToMakePalindrome("aabb"));
// console.log(minMovesToMakePalindrome("letelt"));