diff --git a/CMakeLists.txt b/CMakeLists.txt
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -27,7 +27,7 @@
 find_package(KF5 ${KF5_MIN_VERSION} REQUIRED COMPONENTS
                     Plasma DocTools Runner JsEmbed NotifyConfig Su NewStuff Wallet KCMUtils
                     IdleTime Declarative TextWidgets KDELibs4Support Crash GlobalAccel
-                    DBusAddons Wayland)
+                    DBusAddons Wayland CoreAddons)
 find_package(KF5NetworkManagerQt ${KF5_MIN_VERSION})
 set_package_properties(KF5NetworkManagerQt PROPERTIES DESCRIPTION "Qt wrapper for NetworkManager API"
                        TYPE OPTIONAL
diff --git a/runners/services/CMakeLists.txt b/runners/services/CMakeLists.txt
--- a/runners/services/CMakeLists.txt
+++ b/runners/services/CMakeLists.txt
@@ -12,6 +12,7 @@
 
 add_library(krunner_services MODULE ${krunner_services_SRCS})
 target_link_libraries(krunner_services
+    KF5::CoreAddons
     KF5::KIOWidgets
     KF5::I18n
     KF5::Runner
@@ -21,6 +22,7 @@
 
 add_library(krunner_services_test STATIC ${krunner_services_SRCS})
 target_link_libraries(krunner_services_test
+    KF5::CoreAddons
     KF5::KIOWidgets
     KF5::I18n
     KF5::Runner
diff --git a/runners/services/servicerunner.cpp b/runners/services/servicerunner.cpp
--- a/runners/services/servicerunner.cpp
+++ b/runners/services/servicerunner.cpp
@@ -31,9 +31,25 @@
 #include <KRun>
 #include <KService>
 #include <KServiceTypeTrader>
+#include <kcoreaddons_version.h>
+#if KCOREADDONS_VERSION >= QT_VERSION_CHECK(5, 41, 0)
+#include <KStringHandler>
+#endif
 
 #include "debug.h"
 
+namespace {
+
+int weightedLength(const QString &query) {
+#if KCOREADDONS_VERSION >= QT_VERSION_CHECK(5, 41, 0)
+    return KStringHandler::logicalLength(query);
+#else
+    return query.length();
+#endif
+}
+
+}  // namespace
+
 /**
  * @brief Finds all KServices for a given runner query
  */
@@ -52,6 +68,7 @@
         }
 
         term = context.query();
+        weightedTermLength = weightedLength(term);
 
         matchExectuables();
         matchNameKeywordAndGenericName();
@@ -170,7 +187,7 @@
 
     void matchExectuables()
     {
-        if (term.length() < 2) {
+        if (weightedTermLength < 2) {
             return;
         }
 
@@ -203,7 +220,7 @@
         QVector<QStringRef> queryList = term.splitRef(QLatin1Char(' '));
 
         // If the term length is < 3, no real point searching the Keywords and GenericName
-        if (term.length() < 3) {
+        if (weightedTermLength < 3) {
             query = QStringLiteral("exist Exec and ( (exist Name and '%1' ~~ Name) or ('%1' ~~ Exec) )").arg(term);
         } else {
             //Match using subsequences (Bug: 262837)
@@ -230,7 +247,7 @@
 
             // If the term was < 3 chars and NOT at the beginning of the App's name or Exec, then
             // chances are the user doesn't want that app.
-            if (term.length() < 3) {
+            if (weightedTermLength < 3) {
                 if (name.startsWith(term) || exec.startsWith(term)) {
                     relevance = 0.9;
                 } else {
@@ -330,7 +347,7 @@
 
     void matchJumpListActions()
     {
-        if (term.length() < 3) {
+        if (weightedTermLength < 3) {
             return;
         }
 
@@ -382,6 +399,7 @@
     QList<Plasma::QueryMatch> matches;
     QString query;
     QString term;
+    int weightedTermLength;
 };
 
 ServiceRunner::ServiceRunner(QObject *parent, const QVariantList &args)